My JAVA solution beats over 90% with explanation inline


  • 1
    Q
        public int findNthDigit(int n) {
            // For 1, 2 .., 9, return the result directly
            if(n <= 9){
                return n;
            }
            
            int base = 1;
    
            // Determine the range 
            // 10, 11, ..., 99:  90 * 2 digits in total, base = 2
            // 101, 102, 103, ..., 999:  900 * 3  digits in total, base = 3
            // ...
            while(n > 9 * Math.pow(10, base - 1) * base)
            {
                n = n - 9 * (int)Math.pow(10, base - 1) * base;
                base++;
            }
            
            // Now we should find out which number the answer follows. eg. if the input is 15, the answer should follow on number "12", that's the variable number for.
            int number = (int)Math.pow(10, base - 1) + (n - 1) / base;
    
            // Then we should find out which specific in the number "12". that's what index for, for input 15, index = 0
            int index = (n - 1) % base;
    
            // The answer is the index-th digit of the variable number
            return Integer.toString(number).charAt(index) - '0';
        }
    

  • 0
    W

    Can you explain the n-1 part? really appreciate it.


  • 1
    Q

    @wangbd This is a math problem, I'm not sure I can explain very clearly. So just an example to help you understand.
    Suppose input is 14, then the n is equal to 4 after the while part. We should find out the 4th digit in range 10, 11, 12 ..., 99. The 1st, 2nd goes to number 10 cause 10 = 10 + (1 - 1)/2 and 10 = 10 + (2 - 1)/2 , the 3rd 4th goes to number 11 and so on. Then we can know that the n-th should goes to Math.pow(10, base - 1) + (n - 1) / base. And similar to the calculation of index.


  • 0
    W

    I guess we can say that the "4th digit in range 10, 11, 12 ..., 99" is really the 3rd digit. because after 9, the index of first digit is 0, and second 1, third 2, and fourth 3... so in order to find its index, we do(n-1)/base. It is really hard to explain, but this is as close as I can think of. Thank you for your prompt response


  • 1
    R
    while(n > 9 * Math.pow(10, base - 1) * base)
    ===>
    while(n/base > 9 * Math.pow(10, base - 1))
    

    It may be better to use division for n, as for some data the right part could be larger than Integer.
    The reason it works here is because Math.pow returns a double type, and when doing comparison, n will be cast to double. But for general question, use n/base will be better.

    Anyway, nice solution!


  • 0
    Q

    @rayimpr Great suggestion. Thanks.


  • 0
    M
    public class Solution {
        public int findNthDigit(int n) {
            if(n<10) return n;
            int range=9;
            int previousRange=0;
            int countDigits=1;
            //determine the range of nth digit. 10 to 189 is between 10 and 99, 190 to 2889 is between 100 and 999,etc
            while(n>range)
            {
                previousRange=range;
                range= range+(int)(9*Math.pow(10,countDigits)*++countDigits);
            }
            int value=(n-previousRange-1)/countDigits;
            int index=(n-previousRange-1)%countDigits;
            //get the number
            String number=Integer.toString((int)Math.pow(10,countDigits-1)+value);
            return number.charAt(index)-'0';
            
        }
    }
    

    I think I have the similar idea as you, and when I test with random input, it works.
    However when the test case is 1000000000, it will have "Time Limit Exceeded" error.
    any idea which line of code cause it?


  • 0
    Q

    @momo52620 if you debug your code in some IDE with input 1000000000, you should find out that when countDigits = 9, the range value range= range+(int)(9*Math.pow(10,countDigits)*++countDigits) has a Integer value overflow. You may assign the range to belong to avoid such problem.


  • 0

    Now, this solution runtime beats 40% of java submissions. You never know what's going to happen, haha


Log in to reply
 

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