获取1-N之间1出现的个数

前些天，看见一道笔试题。

题目是获取1-N之间1出现的个数，如N为12，则1-12中含有1的数为｛1，10，11，12｝，

那么1的1-12中，1出现的次数为5。

 

解题的思路是分别对出现在个，十，百，千，万...位上的1进行统计。

以N为31608为例

1. 刚开始是对个位上出现的1进行统计

quo ＝ 31608/10 = 3160

bit ＝ 31608%10 ＝ 8

rem ＝ 31608%1 ＝ 0

由此可见从00001-31601总共有3161个数的个位是1 

 

2. 接着对十位上出现的1进行统计

 

quo ＝ 31608/100 = 316

ten ＝ (31608/10)%10 ＝ 0

rem = 31608%10 = 8

由此可见从00010-31519总共有316*10=3160个数的十位是1

 

3. 接着对百位上出现的1进行统计

 

quo ＝ 31608/1000 = 31

hun ＝ (31608/100)%10 ＝ 6

rem = 31608%100 = 8

由此可见从00100-31199总共有32*100=3200个数的百位是1

 

 

4. 接着对千位上出现的1进行统计

 

quo ＝ 31608/10000 = 3

tho ＝ (31608/1000)%10 ＝ 1

rem = 31608%1000 = 608

由此可见从01000-21999＋ 31000－31608总共有3*1000+609=3609个数的千位是1

 

 

5. 最后对万位上出现的1进行统计

 

quo ＝ 31608/100000 = 0

tth ＝ (31608/10000)%10 ＝ 3

rem = 31608%10000 = 1608

由此可见从10000-19999 总共有1*10000=10000个数的万位是1

 

根据上面的归纳，可以得出

当前计算的位上的数为0，则

该位上出现1的个数＝ quo*当前的位数（情况2）

当前计算的位上的数为1，则

该位上出现1的个数＝quo*当前的位数＋当前计算的位前取最大时剩下的1的个数（情况4）

 

当前计算的位上的数大于1，则

该位上出现1的个数＝(quo+1)*当前的位数（情况1，3，5）

 

根据上述想法，做成的代码如下

/*
 * Create at 2014/09/13 By leehomjan
 */
#include <stdio.h>
#include <stdlib.h>

static int count(int orig)
{
    int div = 1; // divisor
    int count = 0;

    int quo = 0; // quotient
    int curr = 0; // current bit
    int rem = 0; // remainder
    // count 1s in bit ten hundred ...
    while (orig / div) {
        rem = orig%div;
        quo = orig/(div*10);
        curr = (orig/div)%10;

        switch (curr) {
            case 0:
                // orig=20200 div=1000
                // there has 2000 1s in thousand bit
                // they are 01[000...999] and 11[000...999]
                count += quo*div;
                break;
            case 1:
                // orig=20165 div=100
                // there has 2066 1s in hundred bit
                // they are [00...19]1[00...99] + 201[00...65]
                count += quo*div + (rem+1);
                break;
            default:
                // orig=20200 div=100
                // there has 2100 1s in hundred bit
                // they are [00...20]1[00...99]
                count += (quo+1)*div;
        }
        div *= 10;
    }
    return count;
}


static inline int get_count(int from, int to)
{ 
    return count(to) - count(from);
}

int main(int argc, char* argv[])
{
    int from = 0;
    int to = 0;
    int rst = 0;

    if (argc == 1 || argc > 3) {
        printf("./count_1_from_M_to_N {<M> <N>|<N>}\n");
        return 1;
    }

    if (argc == 2) {
        to = atoi(argv[1]);
    } else {
        from = atoi(argv[1]);
        to = atoi(argv[2]);
    }
    rst = get_count(from, to);

    printf("There has %d 1s from %d to %d\n", rst, from, to);

    return 0;
}