LeetCode 400 - Nth Digit

Difficulty: 🟡 Medium
Topics: Math, Binary Search

Solution

Problem Understanding

The problem asks us to find the digit that appears at position n in an infinitely long sequence formed by concatenating all positive integers together.

The sequence looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 ...

If we write it as one continuous string, it becomes:

1234567891011121314...

The input n represents a 1-based index into this infinite sequence. We must return the digit located at that position.

For example:

n = 3
The sequence begins as 123...
The 3rd digit is 3
n = 11
The sequence is 12345678910...
Counting carefully:
digits 1 through 9 come from numbers 1 to 9
digit 10 is 1 from 10
digit 11 is 0 from 10
Therefore the answer is 0

The constraints are important:

1 <= n <= 2^31 - 1

This means n can be extremely large, over two billion. A naive solution that literally builds the sequence digit by digit would be far too slow and memory intensive.

The problem guarantees that n is always valid and positive, so we do not need to handle zero or negative inputs.

Several edge cases are especially important:

Positions near transitions between digit lengths, such as:
9 -> 10
99 -> 100
999 -> 1000
Inputs that land exactly on the last digit of a number
Inputs that land on the first digit of the next number
Very large n, where inefficient simulation becomes impossible

The key challenge is determining which number contains the target digit without generating the entire sequence.

Approaches

Brute Force Approach

The most direct solution is to continuously append integers into a growing string until the string length reaches at least n.

For example:

"1"
"12"
"123"
"1234"
...

Once the string becomes long enough, we simply return the character at index n - 1.

This works because the sequence is constructed exactly as described in the problem statement.

However, this approach is extremely inefficient for large values of n.

If n is close to 2^31 - 1, we would need to generate an enormous string containing billions of characters. Both time complexity and memory usage become unacceptable.

The brute force method is conceptually simple, but it does not scale to the given constraints.

Optimal Approach

The key observation is that numbers contribute digits in predictable groups.

1-digit numbers:
1 to 9
9 numbers
total digits = 9 * 1 = 9
2-digit numbers:
10 to 99
90 numbers
total digits = 90 * 2 = 180
3-digit numbers:
100 to 999
900 numbers
total digits = 900 * 3 = 2700

Instead of constructing the sequence, we can determine which digit-length group contains the target position.

We repeatedly subtract entire groups of digits from n until we find the correct range.

Once we know:

how many digits each number has,
which exact number contains the target digit,
and which digit inside that number we need,

the answer becomes straightforward.

This reduces the problem from constructing billions of digits to performing only logarithmic calculations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds the sequence explicitly
Optimal	O(log n)	O(1)	Skips entire digit ranges mathematically

Algorithm Walkthrough

Start with the group of 1-digit numbers.

Initialize:

digit_length = 1
count = 9
start = 1

These variables represent:

numbers with digit_length digits
how many such numbers exist
the first number in the group

Determine whether the target digit lies inside the current group.

The current group contributes:

$\text{groupDigits} = 9 \times 10^{d-1} \times d$

digits in total.

For example:

2-digit numbers contribute 90 * 2 = 180
3-digit numbers contribute 900 * 3 = 2700

If n is larger than this amount, subtract the entire group and move to the next digit length. 3. Move to the next group when necessary.

After removing one group:

increment digit_length
multiply count by 10
multiply start by 10

This transitions:

from 1-digit numbers to 2-digit numbers
from 2-digit numbers to 3-digit numbers
and so on

Once the correct group is found, identify the exact number containing the target digit.

Suppose:

digit_length = 3
start = 100

Then each number contributes 3 digits.

The target number is:

$\text{number} = \text{start} + \left\lfloor\frac{n-1}{d}\right\rfloor$

We use n - 1 because indexing is easier with zero-based offsets. 5. Determine which digit inside that number is needed.

The digit index is:

$\text{digitIndex} = (n-1) \bmod d$ 6. Convert the number to a string and extract the digit.

This is simple and avoids tricky arithmetic. 7. Return the extracted digit as an integer.

Why it works

The algorithm works because every positive integer belongs to exactly one digit-length group.

By subtracting entire groups, we precisely narrow the search space until the target position lies inside a specific range. Once the correct range is identified, integer division determines which number contains the digit, and modulo arithmetic determines the exact position within that number.

Because every digit in the sequence is accounted for exactly once, the method always returns the correct digit.

Python Solution

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit_length = 1
        count = 9
        start = 1

        # Find the digit-length group containing the nth digit
        while n > digit_length * count:
            n -= digit_length * count
            digit_length += 1
            count *= 10
            start *= 10

        # Find the actual number containing the digit
        number = start + (n - 1) // digit_length

        # Find the digit index within the number
        digit_index = (n - 1) % digit_length

        return int(str(number)[digit_index])

The implementation begins by initializing the 1-digit number range. The while loop repeatedly removes entire groups of digits until the remaining n falls inside the current digit-length category.

For example, if n is larger than all digits contributed by 1-digit numbers, we subtract those 9 digits and move to 2-digit numbers.

Once the correct range is found, the code computes the exact number containing the desired digit using integer division. The offset inside that number is computed using modulo arithmetic.

Finally, the number is converted to a string so the correct character can be indexed directly and returned as an integer.

The implementation uses only a constant amount of extra memory and avoids constructing the enormous infinite sequence.

Go Solution

func findNthDigit(n int) int {
	digitLength := 1
	count := 9
	start := 1

	// Find the digit-length group containing the nth digit
	for n > digitLength*count {
		n -= digitLength * count
		digitLength++
		count *= 10
		start *= 10
	}

	// Find the actual number containing the digit
	number := start + (n-1)/digitLength

	// Find the digit index within the number
	digitIndex := (n - 1) % digitLength

	numberStr := strconv.Itoa(number)

	return int(numberStr[digitIndex] - '0')
}

The Go implementation follows the same mathematical logic as the Python solution.

One important difference is string conversion. In Python, indexing a string directly returns a character string that can be converted with int(). In Go, indexing a string returns a byte, so we subtract '0' to obtain the numeric digit.

The full LeetCode submission also requires this import:

import "strconv"

Go integers are sufficient for the problem constraints because the maximum value remains within 32-bit signed integer range during computation.

Worked Examples

Example 1

Input: n = 3

Initially:

Variable	Value
digit_length	1
count	9
start	1
n	3

Check the loop condition:

3 > 1 * 9 ?

No, so the digit is inside the 1-digit group.

Find the number:

number = 1 + (3 - 1) // 1
       = 1 + 2
       = 3

Find digit index:

digit_index = (3 - 1) % 1
            = 0

Extract digit:

str(3)[0] = '3'

Answer:

Example 2

Input: n = 11

Initial state:

Variable	Value
digit_length	1
count	9
start	1
n	11

First iteration:

11 > 1 * 9

True, subtract the group:

n = 11 - 9 = 2

Move to 2-digit numbers:

Variable	Value
digit_length	2
count	90
start	10
n	2

Check again:

2 > 2 * 90 ?

False.

Now locate the number:

number = 10 + (2 - 1) // 2
       = 10 + 0
       = 10

Digit index:

digit_index = (2 - 1) % 2
            = 1

Extract digit:

str(10)[1] = '0'

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	We iterate through digit-length groups
Space	O(1)	Only a few variables are used

The algorithm only processes groups of numbers based on digit length. Since the number of digit groups grows logarithmically relative to n, the loop executes very few times.

For a 32-bit integer limit, the loop runs at most around 10 iterations because numbers larger than 10 digits are unnecessary.

The space complexity remains constant because no additional data structures proportional to input size are allocated.

Test Cases

solution = Solution()

# Provided examples
assert solution.findNthDigit(3) == 3  # Simple single-digit lookup
assert solution.findNthDigit(11) == 0  # Transition into number 10

# Boundary of single-digit numbers
assert solution.findNthDigit(9) == 9  # Last one-digit number

# Beginning of two-digit numbers
assert solution.findNthDigit(10) == 1  # First digit of 10
assert solution.findNthDigit(12) == 1  # First digit of 11
assert solution.findNthDigit(13) == 1  # Second digit of 11

# Boundary of two-digit numbers
assert solution.findNthDigit(189) == 9  # Last digit of 99

# Beginning of three-digit numbers
assert solution.findNthDigit(190) == 1  # First digit of 100
assert solution.findNthDigit(191) == 0  # Second digit of 100
assert solution.findNthDigit(192) == 0  # Third digit of 100

# Random middle cases
assert solution.findNthDigit(250) == 1  # Digit inside larger range
assert solution.findNthDigit(1000) == 3  # Larger lookup

# Very large input
assert solution.findNthDigit(2147483647) >= 0  # Maximum constraint stress test

Test	Why
`n = 3`	Basic single-digit lookup
`n = 11`	Checks transition from 9 to 10
`n = 9`	Last digit before two-digit numbers
`n = 10`	First digit of first two-digit number
`n = 189`	Final digit of 99
`n = 190`	First digit of 100
`n = 191`	Middle digit of 100
`n = 192`	Last digit of 100
`n = 250`	General non-boundary case
`n = 1000`	Larger input validation
`n = 2147483647`	Maximum constraint stress test

Edge Cases

One important edge case occurs at digit-length transitions such as 9 -> 10 or 99 -> 100. These boundaries are easy places for off-by-one mistakes because the digit count suddenly changes. The implementation handles this correctly by subtracting entire digit groups until n falls within the current group. Using n - 1 for zero-based indexing also prevents indexing errors.

Another critical edge case is when the target digit is the final digit of a number group. For example, position 189 corresponds to the final digit of 99. Incorrect division or modulo logic can accidentally advance into the next number. The algorithm avoids this by computing the number index with integer division using (n - 1) // digit_length.

Very large values of n are also important. Since n may be close to two billion, constructing the sequence explicitly would be infeasible. The mathematical grouping approach ensures the runtime remains extremely small regardless of input size. Only a handful of iterations are needed even for the maximum constraint.