java solution: pre-build a series of ranges and check where the target number falls into


  • 0
    A

    Not the most efficient, but hopefully easier to read with plenty of comments and nice variable names:

    public int findNthDigit(int n) {
        // algorithm: pre-generate a number of ranges, 
        //  each range containing numbers with same number of digits
        //   example: 1, 2, ..., 9            (1 * 9 * pow(10,0))
        //  example: 10, 11, ..., 99         (2 * 9 * pow(10,1))
        //  example: 100, 101, ..., 999      (3 * 9 * pow(10,2))
        //  example: 1000, 1001, ..., 9999   (4 * 9 * pow(10,3))
        //  pow(2, 31): 2,147,483,648: 10 digits
        // first, given n, find its range (thus count of digits)
        // second, find how many numbers ahead (with the same count of digits), thus the target number
        // third, find the digit inside the target number
        
        // use long to avoid integer overflow
        long[] rangeStart = new long[10];
        long[] rangeEnd = new long[10];
        rangeStart[0] = 1;
        rangeEnd[0] = 9;
        long numTens = 10;
        
        int countDigits = 0;
        for (countDigits = 2; countDigits <= 10; countDigits++) {
            rangeStart[countDigits-1] = rangeEnd[countDigits-2] + 1;
            rangeEnd[countDigits-1]   = rangeEnd[countDigits-2] + countDigits * 9 * numTens;
            numTens *= 10;
        }
        
        // find the range and the number
        long numIndex = 0;
        for (countDigits = 1; countDigits <= 10; countDigits++) {
            if (n >= rangeStart[countDigits-1] && n <= rangeEnd[countDigits-1]) {
                numIndex = n - rangeStart[countDigits-1];
                break;
            }
        }
        
        // now we find count of digits and the index of the num, let us find which number is that
        long countNumbersAhead = numIndex / countDigits;
        long targetNumber = (long)(Math.pow(10, countDigits-1)) + countNumbersAhead;
        long digitPlacementInsideNumber = numIndex % countDigits;
    
        // we find the number, now let us find the digit
        String strNum = "" + targetNumber;
        return strNum.charAt((int)digitPlacementInsideNumber) - '0';
    }

Log in to reply
 

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