1的数目

Posted on | In | |
Words count in article: 1.3k | Reading time ≈ 5

给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。

例如：
N = 2， 写下1，2.这样就只有一个“1”。
N = 12， 我们就会写下1，2，3，4，5，6，7，8，9，10，11，12。这样，1的个数是5。

问题：

  1. 写一个函数f(N)，返回1到N之间出现的“1”的个数，比如f(12) = 5;
  2. 满足条件“f(N) = N”的最大的N是多少？

问题一

解法一：

遍历1到N，将每一个数中含有1的个数加起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ULONGLONG Count1InAInteger(ULONGLONG n)
{
    ULONGLONG iNum = 0;
    while(n != 0)
    {
        iNum += (n % 10 == 1) ? 1 : 0;
        n /= 10;
    }
    return iNum;
}

ULONGLONG f(ULONGLONG n)
{
    ULONGLONG iCount = 0;
    for(ULONGLONG i = 1; i <= n; i++)
    {
        iCount += Count1InAInteger(i);
    }
    return iCount;
}

然而这个算法的时间复杂度是O(N*lgN)

当给定的N比较大时候，运算时间就会很长。

要提高效率，必须摒弃遍历的方法。

解法二：

先从一些简单的情况开始观察：

先看1位数的情况：

如果N >= 1， 那么f(N)都等于1，如果N = 0，则f(N)为0

再看2位数的情况：

如果N的个位数大于等于1，则个位数出现1的次数为十位数的数字加1，如果N的个位数为0，则个位出现1的次数等于十位数的数字。

而十位数上出现1的次数也类似：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，如果十位数大于1，则十位数上出现1的次数为10

接着看3位数的情况：

如果 N = 123;
个位出现1的个数为13；
十位出现1的个数为20；
百位出现1的个数为24；

f(123) = 13 + 20 + 24 = 57;

推导一般情况

假设N = abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字，如果要计算百位上出现1的次数，它将受到三个因素的影响，百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。

如果百位上的数字为0，可知，百位上可能出现1的次数由更高位决定，比如12013，百位出现1的情况可能是100~199、1100~1199、2100~2199、、、11100~11199，一共1200个，也就是由更高位数字（12）决定，并且等于更高位数字12*当前位数100。

如果百位上数字为1，可知百位上可能出现1的次数不仅受到更高位影响，还受低位影响，例如12113，受更高位影响，百位出现1的情况是100~199，1100~1199，。。。，11100~11199，一共1200个，等于更高位数字12*当前位数100.但是它还受低位影响，百位出现1的情况是12100~12113，一共14个，等于低位数13+1

如果百位上的数字大于1即2~9，则百位上可能出现1的次数也仅由更高位决定，比如12213，则百位储下你的可能性为100~199、1100~1199、2100~2199、、、11100~11199，12100~12199，一共1300个，并且等于更高位数字加1，再乘以当前位数，即（12+1）*100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LONGLONG Sum1s(ULONGLONG n)
{
    ULONGLONG iCount = 0;
    ULONGLONG iFactor = 1;
    ULONGLONG iLowerNum = 0;
    ULONGLONG iCurrNum = 0;
    ULONGLONG iHigherNum = 0;

    while(n / iFactor != 0)
    {
        iLowerNum = n - (n / iFactor) * iFactor;
        iCurrNum = (n / iFactor) % 10;
        iHigherNum = n / (iFactor * 10);

        switch(iCurrNum)
        {
            case 0:
                iCount += iHigherNum * iFactor;
                break;
            case 1:
                iCount += iHigherNum * iFactor + iLowerNum + 1;
                break;
            default:
                iCount += (iHigherNum + 1) * iFactor;
                break;
        }
        iFactor *= 10;
    }
    return iCount;
}

这个算法，输入长度位Len的数字，时间复杂度为O(Len)，即O(lnn/ln10 + 1)

问题二解法：

要确定最大的数N，满足f(N) = N。

通过上面的算法，可以算得到：

9以下为： 1个

99以下： 20个

999以下：300个

9999以下：4000个

。。。

999999999以下：900000000个

9999999999以下：10000000000个

归纳得到：

f(10^n-1) = n*10^(n-1)。

通过这个递推式，很容易看到，当n = 10^10-1时，f(n)的值大于n，我们可以猜想，当n大于某一个数N时，f(n)会始终比n大，也就是说，最大满足条件在0~N之间，即N是最大满足条件f(n) = n的一个上界。如果能估计出这个N，那么只要让n从N往0递减，每个分别检查是否由f(n) = n，第一个满足条件的数就是我们要求的整数。

因此，问题转化为如何证明上界N确实存在，并估计出这个上界N。

数学归纳法证明得N = 10^11

计算这个最大整数n

令N = 10^11-1 = 99 999 999 999, 让n从N往0递减，依次检查是否有f(n) = n, 第一个满足条件得就是我们要求的整数。

得出n = 1 111 111 110 是满足的最大整数。

扩展问题

对于其他进制表达方式，也可以试一试，看看有什么规律，例如二进制。

暴力遍历？

1 -》1 -》 1

10 -》0+1*2-》2

11 -》1+1*3-》4

100 -》0+1+1*2*2-》5

101 -》1+1+1*2*2-》6

Donate? comment?