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. 考虑134045百位上出现1的个数是多少?

    100-199        —>100
    1100-1199      ->100
    .
    .
    133100-133199  ->100
    总和是:134x100=13400
    
  2. 考虑134145百位上出现1的个数是多少?

    100-199        —>100
    1100-1199      ->100
    .
    .
    133100-133199  ->100
    134100-134145  ->46
    总和是: 134x100+45+1=13446
    
  3. 考虑134245百位上出现1的位数是多少?

    100-199        —>100
    1100-1199      ->100
    .
    .
    133100-133199  ->100
    134100-134199  ->100
    总和是: 134x100+1x100=13500
    

综合上面的分析可得: c代表n的m位上的数,b代表这位前的数(在上面的例子就是134),a代表的这位后的数(上面的例子中就是45)

  • c=0,sum=ax10^m
  • c=1,sum=ax10^m+b+1
  • c>1,sum=ax10^m+10^m

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    
    int countDigitOne(int n) {
        int i;
        int a,b;
        int ones=0;
        for(long long i=1;i<=n;i*=10)
        {
            a=n/i;
            b=n%i;
            switch(a%10)
            {
                case 0: ones+=a/10*i;break;
                case 1: ones+=a/10*i+b+1;break;
                default: ones+=(a/10+1)*i;
            }
        }
        return ones;
    }