Finding pattern based solution Java


  • 0
    Q

    When we have 1 digit (0-9) the maximum number of ones is 1
    When we have 2 digits (0-99) the maximum number of ones is 20
    When we have 3 digits (0-999) the maximum number of ones is 300
    We see a pattern emerging 1,20,300,4000,50000,600000, ....
    Looking for further patterns...

    100,000 => 50,000+1
    110,000 => 50,000+1+10,000  + 4000+1
    120,000 => 50,000+1+20,000  + 4000*2+10,000
    
    1,000,000 => 600,000+1
    1,100,000 => 600,000+1+100,000  +  50,000+1
    1,200,000 => 600,000+1+200,000  +  50,000*2+100,000
    
    1,210,000 => 600,000+1+210,000  +  50,000*2+100,000  +  4,000+1
    1,220,000 => 600,000+1+220,000  +  50,000*2+100,000  +  4,000*2+10,000
    2,130,005 => 600,000*2+1,000,000  +  50,000+30,005+1  +  4,000*3+10,000   +  0*5 +1
    

    A clear pattern is emerging. Only non-zero digits matter, and 1's are to be handled differently from other non-zero digits. We can now come up with a formula, and put it into code.

     public class Solution {
        public int countDigitOne(int n) {
            int count = 0;
            if (n>0){
                String sValue = String.valueOf(n);
                int length = sValue.length();
    
                for (int i=0;i<length;i++){
                    int val = sValue.charAt(i) - '0';
                    int pow= length-i-1;
                    if (val == 1){
                        count = count + (int)Math.pow(10,pow-1)*pow +1;
                        if (i<(length-1)){
                            count = count + Integer.parseInt(sValue.substring(i+1));
                        }
                    }
                    else if (val >0){
                        count = count + (int)Math.pow(10,pow-1)*pow*val + (int)Math.pow(10,pow);
                    }
                }
            }
            return count;
    	}
    }

Log in to reply
 

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