Find digit by calculating how many digits before it


  • 1
    S

    If you get 1 digit, you have 9 numbers, if you have 2 digits, you have 99-10+1 = 90 numbers,
    similarly, 3 digits 900 numbers = (999 - 100 + 1).. if you have i digits you have 9*(10, i-1) numbers.
    total positions is i * 9 * pow(10, i-1). So by keep subtracting positions, you can find the target position located in which digit range and by divide the digit you will find the number, and the remains will be the position you want. ex: n = 96. 1 digit has 9 positions, 96 - 9 = 87. 2 digits has 2*90=180 positions, and 87 < 180. so target number must be in 10...99. (87-1)/2 = 43. so the number is the 44th one from 10. num = 10+43=53.
    (87-1)%2 = 0. so the target digit is 5 of 53

        int findNthDigit(int n) {
            int i = 1;
            while (n > i * 9 * pow(10, i-1)) {
                n -= i * 9 * pow(10, i-1);
                i++;
            }
            int num = pow(10, i-1) + (n-1) / i;
            int k = (n-1) % i;// k = 0..i-1;
            return (num / (int)pow(10, i-k-1)) % 10;
        }
    

  • 0

    @singku this solution is very nice and easy to understand, just one thing, the i9pow(10, i-1) in the while loop's check may be overflow


Log in to reply
 

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