Intuitive solution with detail explanation


  • 3
    C
    public class Solution {
        public int countDigitOne(int n) {  
            if(n <= 0) return 0;
            int res = 0;
            long weight = 1;    //1,10,100,1000,10000...
            long lowerNum = 0;  
            int curDigit = 0;
            long higherNum = 0;
            while (n / weight != 0){
                lowerNum = n % weight;
                curDigit = (int)(n / weight) % 10;
                higherNum = n / (weight * 10);
                
                if(curDigit>1)res += higherNum * weight + weight;
                else if(curDigit==1)res += higherNum * weight + (lowerNum+1);
                else res += higherNum * weight;
                weight *= 10;
            }
            return res;
        }
    }
    
    
    //consider n=2015: check the option of xxx1, xx1z, x1zz, 1zzz, sum them up
    //(1)consider 5: higherNum = 201; curDigit = 5; lowerNum = 0; weight = 1;
    //      choice of xxx1: xxx from 000 to 201 => (higherNum+1)*weight
    
    //(2)consider 1: higherNum = 20; curDigit =1; lowerNum = 5; weight = 10
    //      choice of xx1z: (a)xx from 0 to 19, z from 0 to 9  => higherNum*weight
    //                      (b)xx is 20       , z from 0 to 5  => lowerNum + 1
    
    //(3)consider 0: higherNum = 2; curDigit = 0; lowerNum = 15; weight =100
    //      choice of x1zz: (a)x from 0 to 1,   z from 0 to 99 => higherNum*wiehgt 
    //                      (b)x is 2         , 21zz > 2015    => 0
    
    //(4)consider 2: higherNum = 0; curDigit = 2; lowerNum = 015; weight = 1000
    //      choice of 1zzz: (a)no x(x==0)     , z from 000 to 999 => (higherNum+1)*weight

Log in to reply
 

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