Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1: 

1
2
3
4
5
Input:
3
Output:
3

Example 2: 

1
2
3
4
5
6
7
8
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

思路

利用纯粹的数学方法解决这个问题。

可以从个位一直往上推算，得到一个最大的数字数目之和，将输入数字与该和相减，得到余项。

我们还能得到最大数字所拥有的位数，根据题意推出公式，求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        exp = 0
        after = n
        while (after > 0):
            n = after
            after = after - 9 * 10 ** exp * (exp + 1)
            exp += 1
        remain = n % exp
        pos = n / exp
        print n
        if (exp != 1):
            if (remain == 1):
                res = ( pos / 10 ** (exp-remain)) % 9 + 1
            elif (remain == 0):
                res = ( (pos-1) / 10 ** remain ) % 10
            else:
                res = ( (pos-1) / 10 ** (exp-remain) ) % 10
            return res
        else:
            return n