PU Nth Digit

Find the n^th 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 < 2³¹).

Example:

• Input: 3 Output: 3
• 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.

C Solution:

int findNthDigit(int n) {
    if (n < 10) return n;
    int flag[9] = {0, 9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000};
    int i, res = 0;
    for (i = 1; i < 9 && flag[i] < n; i++) {
        n -= flag[i];
        res += flag[i] / i;
    }
    res += (n - 1) / i + 1;
    n %= i;
    if (!n) return res % 10;
    n = i - n;
    while (n--) res /= 10;
    return res % 10;
}

Summary:

1. find the number first, then find the digit.
2. Be quite careful about the corner case.
3. 3ms, 2.38%.

LeetCode: 400. Nth Digit