Code at the end of the text

1,2,3,4,5,6,7,8,9,10,11,12…………

The above sequence can be divided into N regions

1~9, 10~99, 100~999, …………(10^(n-1))~((10^n) - 1)

The number of digits in each area is as follows

1x9, 2x90, 3x900, 4x9000,…………n*9*(10^n)

The total digits length of 1 to N regions is as follows

9*(1 + 20 + 300 + 4000 ………… + n*(10^n))

when N = 9

9*(1 + 20 + 300 + 4000 ………… + n*(10^n)) = 9*(987654321)

when N = 13

9*(1 + 20 + 300 + 4000 ………… + n*(10^n)) = 9*(13121110987654321)

（The numbers in parentheses are very interesting，After the reversal is 1 2 3 4 5 6 7 8 9 10 11 12 ………… n）

When the input data is the maximum value(2^31)

2^31 = 9*(238609294.2222222) < 9*(987654321)

So we can divide the input number by the value of 9 to determine which region he is in

e.g. input 1000

1000//9 = 111 #the length of 111 is 3， so it belongs to the third or forth region

because 111 < 321 so it belongs to the second region

e.g. input 3269875

3269875//9 = 363319 #the length of 363319 is 6， so it belongs to the sixth or seventh region

because 363319 < 654321 so it belongs to the sixth region

#Because just learning programming soon, the code is not beautiful ( ゜- ゜)つロ

class Solution(object):

def findNthDigit(self, n):

"""

:type n: int

:rtype: int

"""

```
reverse = 0
sum = 0
divideBy9 = n // 9
region = len(str(divideBy9))
for i in range(region):
reverse = (region - i) + reverse * 10 #build a num such as 65421 which length is region
if divideBy9 > reverse:
region += 1
if divideBy9 == reverse and n % 9 > 0:
region += 1
for i in range(region):
reverse = (region - i) + reverse * 10 #build a num such as 65421 which length is (region - 1)
for i in range(region - 1):
sum = (region - i - 1) + sum * 10
sum *= 9
start = pow(10, region - 1)
delta = n - sum
offset = delta % region - 1
targetPlace = start + delta // region
if offset < 0:
offset = region - 1
targetPlace -= 1
targetBit = str(targetPlace)[offset]
return int(targetBit)
```