What is the main pattern used in the Nth Digit problem?

The main pattern is binary search over the valid answer space combined with cumulative digit counting.

How do I avoid off-by-one errors when locating the nth digit?

Carefully track the cumulative digit count and use zero-based indexing consistently when mapping n to the exact number and digit.

Can I generate the sequence up to n to solve this problem?

No, generating the full sequence is infeasible for large n due to memory and time constraints; counting and binary search are required.

What is the time complexity of the optimal solution?

Time complexity is O(log n), mainly from the binary search over digit-length groups and numbers within the target range.

Does this approach work for sequences other than natural numbers?

Yes, with adjustments, the same pattern of cumulative counting and binary search can locate digits in sequences of squares, evens, or other arithmetic sequences.

#400

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

第 N 位数字

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。示例 1：输入： n = 3 输出： 3 示例 2：输入： n = 11 输出： 0 解释：第 11 位数字在序列 1, 2, 3, 4…

数学二分查找

题目描述

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

提示：

1 <= n <= 2³¹ - 1

lightbulb

解题思路

方法一：数学

位数为 $k$ 的最小整数和最大整数分别为 $10^{k-1}$ 和 $10^k-1$ ，因此 $k$ 位数的总位数为 $k \times 9 \times 10^{k-1}$ 。

我们用 $k$ 表示当前数字的位数，用 $cnt$ 表示当前位数的数字的总数，初始时 $k=1$ , $cnt=9$ 。

每次将 $n$ 减去 $cnt \times k$ ，当 $n$ 小于等于 $cnt \times k$ 时，说明 $n$ 对应的数字在当前位数的数字范围内，此时可以计算出对应的数字。

具体做法是，首先计算出 $n$ 对应的是当前位数的哪一个数字，然后计算出是该数字的第几位，从而得到该位上的数字。

时间复杂度 $O(\log_{10} n)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findNthDigit(self, n: int) -> int:
        k, cnt = 1, 9
        while k * cnt < n:
            n -= k * cnt
            k += 1
            cnt *= 10
        num = 10 ** (k - 1) + (n - 1) // k
        idx = (n - 1) % k
        return int(str(num)[idx])

speed

复杂度分析

指标	值
时间	complexity is O(log n) due to binary search over digit-length ranges and numbers within the range. Space complexity is O(1) if using math, or O(log n) if string conversion is employed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate tries to generate the sequence directly instead of using counting or binary search.
question_mark
Candidate struggles to compute cumulative digit counts for each digit length.
question_mark
Candidate miscalculates offsets when mapping n to the correct digit within the target number.

warning

常见陷阱

外企场景

error
Attempting to build the full sequence, which is infeasible for large n.
error
Off-by-one errors when computing cumulative counts or digit offsets.
error
Forgetting that multi-digit numbers contribute multiple digits, leading to wrong indexing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the nth digit for sequences of even numbers only.
arrow_right_alt
Return the nth digit in the concatenation of squares of integers.
arrow_right_alt
Compute the nth digit for a custom base sequence rather than decimal.

help

常见问题

外企场景

继续练习

#367 有效的完全平方数 #441 排列硬币 #483 最小好进制