LeetCode 400: Nth Digit — Python Solution & Explanation

Problem

Leetcode 400 -- Nth Digit

Analysis

Firstly, it's easy to observe that:

• Numbers 0-9 have only 1 digit,
• Numbers 10-99 have 2 digits,
• Numbers 100-999 have 3 digits, and so on.

In other words:
There are 9*1(9e0*1) digits in 1-digit numbers, 90*2(9e1*2) digits in 2-digit numbers, 900*3(9e2*3) digits in 3-digit numbers...

Then we can easily get an array that contains all digits for each group of i-digit numbers
bounds = [9e0, 9e1*2, 9e2*3, 9e3*4, 9e4*5, 9e5*6, 9e6*7, 9e7*8, 9e8*9, 9e9*10, 9e10*11]
This allows us to quickly determine how many digits we need to reach the group that contains the target digit.

Example 1:

n = 10 so it's obvious that 10 could cover 9*1 with 1 remaining, which is not enough to cover 90*2. So when n = 10, the result must be in a 2-digit number and it's the 1st digit of all 2-digit numbers. which is 1 in number 10.

Example 2:

n = 1000 it's also obvious that 1000 could cover 9*1 and 90*2 , with remaining 1000 - 9 - 180 = 811 digits, which is not enough to cover 900*3, so obviously the result mush be in a 3-digit number and it's the 811th digit of all 3-digit numbers.

Solution

Based on the analysis above ,the next steps are clear.
Once we know:

• the digits of the number(digit_range)
• the remaining digits count(remaining_digits) We can find the number that contains the result:

number = 10 ** (digit_range-1) + remaining_digits // digit_range
if remaining_digits % digit_range == 0:
    number = number - 1

note:

if the remaining_digits is exactly divisible by digit_range, number should decrease by one
e.g. digit_range = 2, remaining_digits = 2, the result should be the 2nd digit of the number 10 which is 0
but if we don't minus it would be 10*1 + 2//2 = 11, which is wrong.

Now we get the number, the final step is to get the digit_index of the result within the number, which is quite simple:
digit_index = remaining_digits % digit_range

For easily get the digit of each index, we convert the number into str.
Since Python (and most programming languages) use 0-based indexing,
we can safely convert the number to a string and extract the digit:

numberStr = str(int(number))
return int(numberStr[int(digit_index)-1])

And because in python, index -1 goes to the end of the iterable, so for those remainings that are fully divided by digit_range, the result automatically goes to the last digit, which is compeletely the correct answer.

Full Code

class Solution:
    def findNthDigit(self, n: int) -> int:
        bounds = [9e0, 9e1*2, 9e2*3, 9e3*4, 9e4*5, 9e5*6, 9e6*7, 9e7*8, 9e8*9, 9e9*10, 9e10*11]
        digits = [1,2,3,4,5,6,7,8,9,10]
        digit_range = 0 # how many digits in the number
        for i in range(0,11,1):
            if n > bounds[i]:
                n -= bounds[i]
            else:
                digit_range = digits[i]
                break
        remaining_digits = n
        number = 10 ** (digit_range-1) + remaining_digits // digit_range
        if remaining_digits % digit_range == 0:
            number = number - 1
        digit_index = remaining_digits % digit_range # the index of the digit in the number
        numberStr = str(int(number))
        return int(numberStr[int(digit_index)-1])