#400

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Nth Digit

Given n, efficiently find the nth digit in the infinite integer sequence using a binary search over valid positions.

Problem Statement

You are given a positive integer n and must return the nth digit in the infinite integer sequence formed by concatenating all positive integers: 123456789101112... The challenge is to locate the digit without generating the entire sequence, using math and digit counting.

For example, if n = 3, the output is 3. If n = 11, the output is 0 because the 11th digit corresponds to the second digit of 10 in the sequence. Constraints ensure n is within 1 and 2^31 - 1, requiring an efficient solution.

Examples

Example 1

Input: n = 3

Output: 3

Example details omitted.

Example 2

Input: n = 11

Output: 0

The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

Constraints

1 <= n <= 231 - 1

Solution Approach

Count digit ranges to locate the target group

Compute how many digits exist in 1-digit numbers, 2-digit numbers, etc., cumulatively until the range containing the nth digit is found. This sets the boundaries for binary search over the valid answer space.

Binary search within the digit-length group

Once the correct digit-length group is determined, use binary search over the numbers in that range to pinpoint the exact number that contains the nth digit. Calculate offsets carefully to avoid off-by-one errors.

Extract the exact digit

After identifying the target number, determine the position of the nth digit within it. Convert the number to a string or use mathematical division and modulus to return the correct single digit efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Mathematics

The smallest and largest integers with $k$ digits are $10^{k-1}$ and $10^k-1$ respectively, so the total number of digits for $k$-digit numbers is $k \times 9 \times 10^{k-1}$.

1

2

3

4

5

6

7

8

9

10

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])

Continue Practicing

#367 valid perfect square #441 arranging coins #483 smallest good base