LeetCode 400: Nth Digit

Problem Restatement

We are given an integer n.

Consider the infinite sequence formed by writing positive integers one after another:

123456789101112131415...

We need to return the nth digit in this sequence.

The position is 1-indexed.

For example:

n = 3

The third digit is 3.

For:

n = 11

The sequence begins:

12345678910...

The 11th digit is 0, from the number 10.

Input and Output

Example function shape:

def findNthDigit(n: int) -> int:
    ...

Examples

Example 1:

n = 3

The sequence starts:

1 2 3 4 5 6 7 8 9 ...

The third digit is:

3

Example 2:

n = 11

The sequence starts:

1 2 3 4 5 6 7 8 9 1 0 1 1 ...

The 10th digit is 1, the first digit of 10.

The 11th digit is 0, the second digit of 10.

So the answer is:

0

First Thought: Build the String

A direct solution is to build the sequence until it has at least n digits.

sequence = "123456789101112..."

Then return:

int(sequence[n - 1])

This is easy, but n can be as large as 2^31 - 1.

Building such a long string is too slow and uses too much memory.

We need to jump directly to the right number.

Key Insight

Numbers can be grouped by digit length.

In general, for digit_len digits:

count = 9 * 10^(digit_len - 1)

and the group contributes:

count * digit_len

So we can subtract whole groups until n falls inside one group.

Algorithm

Start with the 1-digit group:

digit_len = 1
start = 1
count = 9

While n is larger than the total digits in the current group:

n -= digit_len * count
digit_len += 1
start *= 10
count *= 10

After this loop, the target digit is inside the group starting at start.

Now n is the position inside that group, still 1-indexed.

Find the exact number:

number = start + (n - 1) // digit_len

Find the digit index inside that number:

index = (n - 1) % digit_len

Return:

int(str(number)[index])

Walkthrough

Let:

n = 11

The 1-digit group contributes 9 digits.

Since 11 > 9, subtract it:

n = 11 - 9 = 2

Now we are in the 2-digit group:

10, 11, 12, ...

The second digit in this group is inside 10.

Compute the number:

start = 10
digit_len = 2

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

Compute the digit index:

index = (2 - 1) % 2
      = 1

The digit at index 1 in "10" is:

"0"

So the answer is:

0

Correctness

The sequence is divided into groups by digit length.

For each digit length d, there are exactly 9 * 10^(d - 1) positive integers with d digits. Therefore that group contributes exactly:

d * 9 * 10^(d - 1)

digits to the infinite sequence.

The algorithm subtracts complete groups while the target position lies after them. When the loop stops, n is the position of the desired digit inside the current digit-length group.

Inside that group, every number contributes exactly digit_len digits. Therefore (n - 1) // digit_len gives the zero-based offset of the target number from start, and (n - 1) % digit_len gives the digit position inside that number.

Thus number = start + (n - 1) // digit_len is exactly the number containing the target digit, and index = (n - 1) % digit_len is exactly the target digit’s index inside that number.

Returning that digit gives the correct nth digit of the infinite sequence.

Complexity

For 32-bit n, there are at most 10 digit-length groups.

Implementation

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

        while n > digit_len * count:
            n -= digit_len * count
            digit_len += 1
            start *= 10
            count *= 10

        number = start + (n - 1) // digit_len
        index = (n - 1) % digit_len

        return int(str(number)[index])

Code Explanation

We begin with the 1-digit group:

digit_len = 1
start = 1
count = 9

digit_len is the number of digits per number in the current group.

start is the first number in that group.

count is how many numbers are in that group.

This loop skips full groups:

while n > digit_len * count:

After skipping a group, we move to the next digit length:

n -= digit_len * count
digit_len += 1
start *= 10
count *= 10

When the loop ends, the answer is inside the current group.

The target number is:

number = start + (n - 1) // digit_len

The target digit position inside that number is:

index = (n - 1) % digit_len

Finally:

return int(str(number)[index])

Testing

def test_solution():
    s = Solution()

    assert s.findNthDigit(1) == 1
    assert s.findNthDigit(3) == 3
    assert s.findNthDigit(9) == 9
    assert s.findNthDigit(10) == 1
    assert s.findNthDigit(11) == 0
    assert s.findNthDigit(12) == 1
    assert s.findNthDigit(13) == 1

    assert s.findNthDigit(189) == 9
    assert s.findNthDigit(190) == 1
    assert s.findNthDigit(191) == 0
    assert s.findNthDigit(192) == 0

    assert s.findNthDigit(1000) == 3

    print("all tests passed")

test_solution()

Test meaning: