My Java Solution with explation


  • 1
    S
     /**
     *每个位置分别处理,
     * 120
     * 120/ 10 = 12 没有余数 ,不处理
     * 120/100 = 1 .... 20   十位 1 的个数为 1* 10 + 10(因为 20> 19,如果 20 <= 19 例如 17 。则需要加上 17%10 + 1 即 8)
     * 120/1000 = 0 .... 120  百位的1的个数为 120 % 100 +1 = 21
     * 因此总个数为  12 + 20 + 21 = 53
     * 
     * calculate every digit
     * e.g.
     * 120
     * single digit :120/10=12  no rest
     * 
     * ten digit : 120/100 = 1 ....20   ten digit counts 1* 10 + 10(because 20 / 10 = 2 witch is bigger than 1; if it is 17,than ten digit should be 1*10 + 17%10 +1 = 18)
     * 
     * hundreds digit : 120/1000 = 0 .... 120       0*100 + 120%100+1 = 21
     * 
     * so the result is 12 +20 + 21;
     * 
     * when compairing the nums it might be bigger then Integer.MAX_VALUE,so here I use 'long';
     */
    public int countDigitOne(int n) {
        long nPlus = n;
        int count = 0;
        long x = 10;
        while(nPlus * 10 >= x){
            count += calcHelper(nPlus,x);
            x*=10;
        }
        return count;
    }
    public long calcHelper(long n,long x){
        long high = n/x * x/10;
        long mod =  n%x;
        if(mod / (x /10) < 1 ){
            return high;
        }
        if(mod / (x /10) > 1){
            return high + x/10;
        }
        return high + mod % (x/10) +1;
    }

Log in to reply
 

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