Straight-forward 6-line c++ solution with explanation


  • 0

    We can easily come up with the following regularity:
    [1-10): 1 digit number, 9 numbers, 9 digits in total
    [10-100): 2 digit number, 90 numbers, 180 digits in total
    [100-1000): 3 digit number, 900 numbers, 2700 digits in total
    [first-first * 10): k digit number, 9 * first numbers, 9 * k * first digits in total

    Before the loop we make n 0-based for easier computation. During the loop we check for the correct range for n. As long as we find the destination range (n < 9 * k * first) we return the result by shifting the correct digit to the least significant digit then mod 10.

    int findNthDigit(int n) {
        n--;
        for (int k = 1, first = 1; ; k++, first *= 10) {
            if (n / 9 / k < first)
                return (first + n / k) / (int)pow(10, k - 1 - n % k) % 10;
            n -= 9 * k * first;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.