Intuitive solution with comments


  • 9
    We are tightening the range of our target gradually.
    1. Is this number that has nth digit between 100~999, 1000~9999 or some other range?
    2. What is this number?
    3. Within thin number, which digit is the nth digit?
    
    number of the digits at each "level"
    1-9: 9 digits
    10-99 : 90 * 2 = 180 digits 
    100-999 : 900 * 3 = 2700 digits
    1000-9999 : 9000 * 4 = 36000 digits
    ....
    */
    public class Solution {
        public int findNthDigit(int n) {
            if(n < 1) return 0;
            if(n < 10) return n;
            int counter = 1;  //stores the level number
            int base = 0;      //stores the biggest number from previous level
            while(n > (9 * Math.pow(10,counter -1) * (counter))){
                base += 9 * Math.pow(10,counter -1);
                n -= (9 * Math.pow(10,counter -1) * (counter));
                counter++;
            }
            //target is the actual number that has nth digit
            int target = base + ((n + counter - 1) / counter);  //to get the ceiling of n / counter
            int offset = n % counter;
            offset = (offset == 0) ? 0:counter - offset;
            for(int i = 0; i < offset; i++){
                target = target / 10;
            }
            return target % 10;
        }
    }

  • 0
    H

    How did you determine what target was? Like, what's the thought process for determining that formula?


  • 1

    @helloruiz

    Let's say you want to know what's 14th digit is, i.e n = 14
    after this part

    while(n > (9 * Math.pow(10,counter -1) * (counter))){
                base += 9 * Math.pow(10,counter -1);
                n -= (9 * Math.pow(10,counter -1) * (counter));
                counter++;
            }
    

    n will be 14 - 9 = 5(digits) and base will be the number 9.
    so we know the nth number is 5 digits from the number 9.
    since from number 10, every number has 2 digits, the number that has 14th digit is 9 + ceiling(5/2) = 12
    so we know number 12 has the 14th digit


  • 0
    E

    My idea is similar, but i chosen summation .

    get summation digits . we no need to go for a loop. it is simple observation
    1= 9
    2=> 189 (9+ 90 *2)
    3 =>2889(9 + 180+ 900 *3)
    so pattern is for ith digits Summation Σi = (i-1) 8 appears (i-1) times followed by 9
    here first digit is i-1, last digit is 9 and in-between there are i-1 8s.
    4==> 3 888 9=38889
    8==> 788888889

    Approach is :: get the length-1 of the number ,get the summation subtract input number with this to get a number which will be divided by length of the current number length
    for example: 4000 is input.
     so get the summation of 3(length-1) which is 2 88 9. 4000-2889 = 1111 
     999 + 1111/4 = 266 ,with remainder 3. so  third digit of 277 which is 7 is the answer

Log in to reply
 

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