400. Nth Digit

Find thenthdigit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

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

Example 1:

Input:3
Output:3

Example 2:

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.

S: math 观察找规律

9*10^0个1位数：1,2,...,9

9*10^1个2位数：10, 11,...,99

9*10^2个3位数：100, 101..,999

...

注意overflow

    int findNthDigit(int n) {
        int len = 1;
        for (long k = 9; n - len * k > 0; k *= 10) {  //找到nth所在的位数，注意k为int可能overflow
            n -= len * k;
            len++;
        }
        long num = pow(10, len - 1) + (n - 1) / len;  //计算nth所在的数字
        int digit = (n - 1) % len;  //计算nth在该数字的第几位
        string s = to_string(num);  //转化为string直接求得
        return s[digit] - '0';
    }