Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路:统计所有数中,各数位上1的个数。可以用循环的方式,从小达大对每个数位上1的个数进行统计。

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)
            return 0;
       int count = 0;
       for(long base = 1; base <= n; base *= 10)     // long, base*10 可能溢出
       {
           long data = n/base;
           long remain = n%base;
           count += (data+8)/10*base;               //  =0, =1, >1
           if(data%10 == 1)                        //  =1
              count += remain+1;
       }
       return count;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *