解法一： 一个几乎纯数学的解法
numbers: 1,...,9, 10, ..., 99, 100, ... 999, 1000 ,..., 9999, ...
# of digits: 9 + 90*2 + 900*3 + 9000*4 + ...
利用这个公式可以很容易的求出来Nth digit出现在一个几位数上。假设出现在一个4位数上。那么我们应该从1000的第一个1开始往后数 n - (9 + 90*2 + 900*3)个digits。那么第n个digits应该出现在那个4位数上呢？可以用L17算出来这个数是1000后面的第几个自然数， e.g. 5。res为最后剩余的digits的个数，这个res<=4。那么我们应该找 '1005' 中的第res-1个digit。
class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
sum = 0
i = 1
while n > sum + i*9*10**(i-1):
sum += i*9*10**(i-1)
i += 1
start = 10**(i-1)
step = (n - sum - 1)//i
res = n - sum - step*i
return int(str(start + step)[res-1])