6ms Java Solution


  • 0
    L

    I have to figure out the faster way since Leetcode does not accept dumb way.

    public int findNthDigit(int n) {
        //build talbe
        long[] table = BuildTable();
        
        // find corresponding interval
        int intervalID = 0;
        for (int i = 0 ; i < 10 ; i ++) {
            if (n < table[i]) {
                intervalID = i - 1;
                break;
            }
        }
        
        // initialization
        int subLen = intervalID + 1;
        int start = (int) Math.pow(10, intervalID);
        int startN = (int) table[intervalID];
        int countN = n - startN;
        
        // locate the int
        int target = start + countN / subLen;
        
        // obtain the result;
        StringBuilder sb = new StringBuilder(target + "");
        int index = countN % subLen;
        int result = Character.getNumericValue(sb.charAt(index));
        
        return result;
    }
    
    private long[] BuildTable() {
        // each index is the number of total digits less than 10^i
        long[] result = new long[10];
        result[0] = 1;
        int i = 1;
        while (i <= 9) {
            long nrOfInt = (int) (Math.pow(10, i) - Math.pow(10, i - 1));
            result[i] += nrOfInt * i;
            result[i] += result[i - 1];
            i ++;
        }
        return result;
    }

Log in to reply
 

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