Beats 89.41%. Java Solution Explained In Detail


  • 0
    K
    /**
     * 
     * Explanation:
     * Lets consider the range of numbers based of digits. 
     * For example the number of digits for numbers ranging 1-9 is 1
     * 			   the number of digits for numbers ranging 10-99 is 2
     *  		   the number of digits for numbers ranging 100-999 is 3 and so on
     * 
     * Now, Lets see the total count of digits present for these ranges
     * For example the total number of digits for numbers ranging 1-9 is 9
     * 			   the total number of digits for numbers ranging 10-99 is 180
     * 			   the total number of digits for number ranging 100-999 is 2700
     * The pattern observed in the total number of digits is as follows:
     * 9, 180, 2700,36000 => (3^2)*(10^0)*1, (3^2)*(10^1)*2, (3^2)*(10^2)*3, (3^2)*(10^3)*4
     * Therefore, the formula is Math.pow(3, 2) * Math.pow(10, i) * (i+1)
     * 
     * Using this formula, we can calculate the digit range for every number range.
     * For example, the digit range for 10-99(99=10^2-1) is 10-189(189=180+9)
     * 				the digit range for 100-999(999=10^3-1) is 190-2889(2889=2700+189) and so on
     * 
     * Now that we know the digit ranges that correspond to the number ranges, its easy to find the Nth digit.
     * For a given n, find the range the digit falls under.
     * For example, 21st digit falls under 10-189 range.
     * To identify the 21st digit, we need to subtract 21 from 10. This gives us the number of digits we need to move.
     * Since we also know that for 10-99 range, moving 2 digits is equivalent to 1 number, 
     * we can simply compute quotient and remainder for the number of digits we need to move, which is 11(21-10)
     * 
     * Therefore, the quotient is 5 and the remainder is 1.We add 5 to minimum number in the range which is 10.
     * Therefore the number is 10+5=15. And since remainder is 1, its number at 1st index. 
     *
     */
    public class NthDigit {
    
        public int findNthDigit(int n) {
        	if(n < 10) return n;
        	
            int i=1;
            int minDigit = 10;
            int maxDigit = (int) (Math.pow(3, 2) * Math.pow(10, i) * (i+1) + minDigit - 1);
            
            while(n > maxDigit) {
                minDigit = maxDigit + 1;
                i++;
                maxDigit = (int) (Math.pow(3, 2) * Math.pow(10, i) * (i+1) + minDigit - 1);
            }
            
            int minN = (int) Math.pow(10, i);
            int moves = n - minDigit;
            int add = 0, modulo = 0;
            if(moves >= i+1) {
            	add = moves/(i+1);
            	modulo = moves%(i+1);
            }else {
            	modulo = moves;
            }
            int finalN = minN + add;
            char[] chars = ("" + finalN).toCharArray();
            return Character.getNumericValue(chars[modulo]);
        }
    }
    

Log in to reply
 

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