requirements

Give you an integer n, ask you in an infinite sequence of integers [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,…] Find and return the NTH digit.

Example 1:

Input: n = 3 Output: 3Copy the code

Example 2:

Input: n = 11 Output: 0 Explanation: 11th digit in sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11... It's 0, it's part of 10.Copy the code

The core code

class Solution:
    def findNthDigit(self, n: int) - >int:
        flag,m = 9.9
        i = 1
        if n <= 9:
            return n
        while m < n:
            i += 1
            res = m
            m += flag * 10 ** (i -1) * i
        if (n - res) % i == 0:
            return int(str(10 ** (i - 1) + (n - res) // i -1)[-1])
        else:
            return int(str(10 ** (i - 1) + (n - res) // i)[(n - res) % i - 1])
Copy the code

Timeout code

class Solution:
    def findNthDigit(self, n: int) - >int:
        if n < 1:
            return 
        res = [str(i) for i in range(1,n + 1)]
        string = "".join(res)
        res = list(string)
        return int(res[n - 1])
Copy the code

We take n numbers and add them together, and then extract the NTH character of the string. Core code:

  • Determine the number of digits in the NTH digit: 1-9 is a single digit and 10-99 is a two-digit number9+ (99-10 + 1) * 2… And so on, in the code, we can calculate how many digits up to the i-th digit, if greater than n, it means that n is in an I-digit
  • If n = 15 is the second place of the third 2-digit number (12), the 15th digit is 2.I is the number of digits in the NTH digit.Res indicates how many digits precede the i-1 digits.N-res indicates how many bits there are in an i-digit number.(n-res) divisible by I determines the number in which n is.N-res mod I to determine what digit I is in that number

In self Understanding: Part I: We can see from the above while loop that when we add two digits, we add (99-10+1)*2 = 90 *2, which is when we add three digits, The number of bits we added is (999-100+1)*3 = 900 *3, so what we extract is flag * 10 ** (i-1)* I, very neat formula. Part II: Let’s say our number is 124, we go into the loop, I = 2,res=9,m =189>n, we jump out of the loop, we say I is the current two-digit number, n(124) -res (9) = 115, minus the space of the 1-digit number, and then we want to know in which digit, (n-res)// I yields the number in, (124-9)//2 = 57, assuming (n-res) % I == 0, the last digit of the current number, assuming (n-res) % I! Lambda is equal to 0, and we have to figure out what digit he is in, so that’s the interpretation of the scarlet letter up there.