给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。
例如：
N = 2，写下1，2。这样只出现了1个“1”。
N = 12，我们会写下1,2,3,4,5,6,7,8,9,10,11,12。这样，1的个数是5。
问题是：
- 写一个函数f(N)，返回1到N之间出现的“1”的个数，比如f(12) = 5；
- 满足条件“f(N) = N”的最大的N是多少？
对于问题1，最简单最直接的方法就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来。
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) * 计算一个整数数字里面“1”的个数的复杂度 = O(N*lgN)。
这样的算法，应该是直接抛弃的…
换一个角度，可以分析“小于N的数在每一位上可能出现1的次数”之和来求解。
对于1位数的情况，
如果N = 3，那么从1到3的所有数字：1、2、3，只有个位数字上可能出现1，而且只出现1次，进一步可以发现如果N是个位数，且N>=1， 那么f(N)都等于1。
对于2位数的情况，
个位数只有1、11、21、31等这样的情况
显然，
如果N的个位数大于等于1，则个位出现1的次数为十位数的数字+1；
如果N的个位数为0，则个位数出现1的次数为十位数的数字。
十位数上出现1的情况只有10、11、12、13等这样的情况
显然，
如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1；
如果十位数字大于1，则十位数上出现1的次数为10。
按照同样的规则进行推理3、4、5位数的情况。
对于一般情况下，从N得到f(N)的计算方法。
假设N = abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字。
如果要计算百位上出现1的次数，它将会受到三个因素的影响：
百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。
如果百位上的数字为0，那么百位上可能出现1的次数由更高位决定。
百位上可能出现1的情况 100~199,1100~1199,2100~2199，很明显，等于更高位的数字 * 当前的位数。
如果百位上的数字为1，显然，百位上可能出现1的次数不紧受更高位的影响，还受低位影响，高位影响同上，等于高位数字 * 当前位数；受低位影响，比如12113，等于低位数字+1 （13+1）。
如果百位上数字大于1，很明显，百位数字上没有提供1，不过却间接的又多提供了当前的位数个1。因此百位数出现1的情况等于 更高位数字加1，再乘以当前位数。
LONGLONG Sun1s(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 * Factor; break;
case 1: iCount += iHigherNum * Factor + iLowerNum + 1; break;
default: iCount += (iHigherNum + 1) * iFactor; break;
}
iFacotr *= 10;
}
return iCount;
}
时间复杂度为 O(strlen(N))；N的长度
对于问题2，一个简单的分析
9以下为： 1个；
99以下为： 1*10 + 10 * 1 = 20个 //十位数出现1的个数+个位数出现1的个数
999以下为： 1*100 + 10 * 20 = 300个；
9999以下为： 1*1000 + 10 * 300 = 4000个；
归纳的 f(10n – 1) = n * 10 n-1。当n = 1010 – 1时，f(n)=1010的值大于n。
我们可以猜想，当n大于某一个数N时，f(n)会始终比n大。
也就是说，N是最大满足条件f(n) = n 的一个上界。
下面证明满足条件f(n) = N 的数存在一个上界。
当n增加10时，f(n)至少增加1；
当n增加100时，f(n)至少增加20；
当n增加1000时，f(n)至少增加300；
当n增加10 000时，f(n)至少增加4 000；
……
f(10) = 2；
f(100) = 1 + 1 * 10 + 10 * 1 = 21；
f(1000) = 1 + 1 * 100 + 10 * 10 + 100 * 1 = 301;
拿10来说，本身含两个1，一般情况下一个n+1多增加一位，除了0、10这样能增加2或10位的。。抛出1这个数字与特殊情况，当增加1-时，f(n)至少增加1；
类似，当n增加10k时，f(n)至少增加k*10k-1。
当n按十进制展开，n = a*10k + b*10k-1 + …，
f(n) = f(0 + n) = f (0 + a*10k + b*10k-1 + …) > a*k*10k-1 + b*(k-1)*10k-2。
又 n = a*10k + b*10k-1 + … < a*10k + (b+1)*10k-1
现在我们想证f(n)>n。
如果a*k*10k-1 + b*(k-1)*10k-2 >= a*10k + (b+1)*10k-1即得证。
即 10*a*k + b *k – b – 100 *a – 10*b – 10 >=0 ;
(10 * a + b )*k >= b + 10 + 100*a+10*b ;
k >= 10 + (b + 10)/(b + 10 *a);
k>11
即n的整数位大于等于12时，f(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是满足f(n) = n的最大整数。
扩展问题
对于其他进制表达方式，也可以试一试，看有什么规律。例如二进制：
f(1) = 1
f(10) = 10 （因为 01， 10 有两个1）
f(11) = 100 （因为01,10,11有四个1）
其实思路还是一样的，还是分别考虑右侧第一位上出现1的次数、右侧第二位上出现1的次数…依次类推
先考虑最低位的1，显然，第一位上的1每两个数出现一次。 N/2 + N%2 + 1 – 2/2
再考虑低2位的1，每四个数出现两个1。 N/4 *2+ N%4 + 1 – 4/2
依次类推，低三位，每八个数出现四个1，低四位，每十六个数出现八个1。 N/8 *4+ N%8 + 1 – 8/2
00 01 10 11 100 101 110 111 1000
公式已经出来了 低k位上1的各位为 N/2^k * 2^(k-1) + N%(2^k) + 1 – 2^k/2
其中+1是因为从0开始算起的，在取模的时候需要+1右移一下。
一个有意思的现象， 对于N = 111…110这样的数，即a个1加一个0组成的数，
f(N) = a个a(a+1)。 如f(1110) = 444, f(11111110) = 8888888。