google面试题及我的算法（2）——0~n之间1的个数（完美版）

本博客（http://blog.csdn.net/livelylittlefish）贴出作者（三二一、小鱼）相关研究、学习内容所做的笔记，欢迎广大朋友指正！

Problem

 

Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

 

1. 思考

 

1位数：0~9
       个位数为1：1，共1次
       故0~9之间，1的个数为1

2位数：10~99

       个位数为1：11, 21, 31, …, 91，共9次
       十位数为1：10, 11, 12, …, 19，共10次

       故0~99之间，1的个数为1+9+10=20次

 

       也可以这样考虑：
       在0~99之间个位有10个0~9，故有10*1=10次，而十位为1的有10次，共20次
       20=10*1+10

 

3位数：100~999
       个位数为1：101, 111, 121, …, 191  ——  10个
                             201, 211, 221, …, 291  ——  10个
                             …
                             901, 211, 221, …, 291  ——  10个
                             共9个10，是90次

 

       十位数为1：110, 111, 112, …, 119  ——  10个
                             210, 211, 212, …, 219  ——  10个
                             …
                             910, 911, 912, …, 919  ——  10个
                             共9个10，是90次

 

       百位数为1：100, 101, 102, …, 199  ——  100个
                             共100次

 

       故0~999之间，1的个数为20+90+90+100=300次

 

       也可以这样考虑：
       0~999之间：十位个位共有10个0~99，故有10*20=200次，而百位为1的有100次
       共200+100=300次
       300=10*20+100

 

4位数：1000~9999
       个位数为1：1001, 1011, 1021, …, 1091  ——  10个
                             1101, 1111, 1121, …, 1191  ——  10个
                             1201, 1211, 1221, …, 1291  ——  10个
                             …
                             9001, 9011, 9021, …, 9091  ——  10个
                             …
                             9801, 9811, 9821, …, 9891  ——  10个
                             9901, 9911, 9921, …, 9991  ——  10个
                             共90个10，是900次

 

       十位数为1：1010, 1011, 1012, …, 1019  ——  10个
                             1110, 1111, 1112, …, 1119  ——  10个
                             1210, 1211, 1212, …, 1219  ——  10个
                             …
                             9010, 9011, 9012, …, 9019  ——  10个
                             …
                             9810, 9811, 9812, …, 9819  ——  10个
                             9910, 9911, 9912, …, 9919  ——  10个
                             共90个10，是900次

 

       百位数为1：1100, 1101, 1102, …, 1199  ——  100个
                             2100, 2101, 2102, …, 2199  ——  100个
                             …
                             9100, 9101, 9102, …, 9199  ——  100个
                             共9个100，是900次

 

       千位数为1：1000, 1001, 1002, …, 1999  ——  1000个
                             共1000次

 

       故0~9999之间，1的个数为300+900*900*900+1000=4000

 

       也可以这样考虑：
       0~9999之间：百位十位个位共有10个0~999，故有10*300=3000次，而千位为1的有1000次
       共3000+1000=4000次
       4000=10*300+1000

 

2. 规律

 

       为方便观察，将这些数据列出，如下：

       0~9：1
       0~99：20=10*1+10
       0~999：300=10*20+100
       0~9999：4000=10*300+1000
       0~99999：50000=10*4000+10000
       0~999999：600000=10*50000+100000
       …

 

       从中，我们不难发现规律：

       a₁=1
       a₂=10*a₁+10
       …
       a_m=10*a_m-1+10^m-1
 

      即0~9…9（m个9）之间1的个数为a_m=10*a_m-1+10^m-1个；

 

3. 实际计算

 

       找到这些规律并不难，可是对于任意给定的数n，怎样能快速得到0~n之间1的个数呢？

 

       例如，n=1234，计算步骤如下：
       (1) 将0~1234分为2个部分：0~999，1000~1234；
       (2) 有1个0~999，共300次；
       (3) 应该加上千位为1的次数，共234+1次，即n%1000+1=235次；
       (4) 此时，就剩下0~234了，不满1个0~999，故继续拆开：0~99，100~199，200~234；共有2个0~99，共2*20=40次；
       (5) 因百位数为2>1，故应该加上百位为1的次数，共100次；（从拆分的结果也很容易得出）
       (6) 此时，就剩下200~234了，实际上就是剩下0~34了，不满1个0~99，故继续拆开：0~9，10~19，20~29，30~34；共有3个0~9，共3*1=3次；
       (7) 因十位数为3>1，故应该加上十位为1的次数，共10次；
       (8) 此时，就剩下30~34了，实际上就是剩下0~4了，共1次（即因个位数为4>1，故应该加上个位为1的次数，共1次）；

      

       故0~1234之间1的个数为300+235+40+100+3+10+1=689个

 

       如果，某个位的数字为1或者0，情况又是怎样呢？

 

       例如，n=20140，计算步骤如下：
       (1) 将0~20140分为3个部分：0~9999，10000~19999，20000~20140；
       (2) 有2个0~9999，共2*4000=8000次；
       (3) 应该加上万位为1的次数，共10000次，
       (4) 此时，就剩下0~140了，不满1个0~999，故拆为0~99，100~140；共有1个0~99，共1*20=20次；
       (5) 因百位为1=1，故应该加上百位为1的次数，共40+1次，即n%100+1=41次；
       (6) 此时，就剩下0~40了，共有4个0~9，共4*1=4次；
       (7) 因十位为4>1，故应该加上十位为1的次数，共10次；
       (8) 此时就剩下40了，实际上就是0，共0次；

 

       故0~20140之间1的个数为8000+10000+20+41+4+10=18075

 

4. 求解算法

 

-	5	4	3	2	1	0
a	50000	4000	300	20	1	0
x	-	1	2	3	4	Empty

 

       n=1234，0~n之间1的个数计算方法如下：

       count = 0

 

       count += x[4] * a[3] + 1000,             if x[4] > 1
       count += x[4] * a[3] + n%1000 + 1, if x[4] = 1

 

       count += x[3] * a[2] + 100,             if x[3] > 1
       count += x[3] * a[2] + n%100 + 1, if x[3] = 1

 

       count += x[2] * a[1] + 10,             if x[2] > 1
       count += x[2] * a[1] + n%10 + 1, if x[2] = 1

 

       count += x[1] * a[0] + 1,             if x[1] > 1
       count += x[1] * a[0] + n%1 + 1, if x[1] = 1

 

       即count += x[4] * a[3] + (x[4]>1) ? 1000 : ((x[4] =1) ? (n%1000 + 1) : 0)
           count += x[3] * a[2] + (x[3]>1) ? 100 : ((x[3] =1) ? (n%100 + 1) : 0)
           count += x[2] * a[1] + (x[2]>1) ? 10 : ((x[2] =1) ? (n%10 + 1) : 0)
           count += x[1] * a[0] + (x[1]>1) ? 1 : ((x[1] =1) ? (n%1 + 1) : 0)

 

5．源程序

[c-sharp] view plaincopy

1. /************************************************************************ 
2. * 0~n之间1的个数,如f(13)=6 
3. * 1,2,3,4,5,6,7,8,9,10,11,12,13.1的个数为6 
4. * 要求:输入一个正整数n,求出f(n),及求解f(n)=n 
5. ************************************************************************/ 
6.  
7. #include <stdio.h>   
8. #include <string.h>   
9. #include <Windows.h>    
10.   
11. class CalculationTimes  
12. {  
13. public:  
14.     CalculationTimes(){}  
15.     ~CalculationTimes(){}  
16.   
17.     long long GetTimes(long long n);  
18. };  
19.   
20. //计算正整数n中1的个数    
21. long long CalculationTimes::GetTimes(long long n)  
22. {  
23.     long long count=0;  
24.   
25.     //0     :0    
26.     //0~9   :1    = 10 * 0   + 1    
27.     //0~99  :20   = 10 * 1   + 10    
28.     //0~999 :300  = 10 * 20  + 100;    
29.     //0~9999:4000 = 10 * 300 + 1000    
30.     long long a=0;      //0,1,20,300,4000,...    
31.     long long weight=1; //1,10,100,1000,...    
32.       
33.     int x;          //数的当前位    
34.   
35.   
36.     long long temp=n;  
37.     while(temp)  
38.     {  
39.         x=temp%10;  
40.   
41.         count+=x*a;  
42.   
43.         //加上当前位为1的个数    
44.         if(x>1)         //若该位>1，则当前位为1的个数为10^(m-1)    
45.             count+=weight;  
46.         else if(x==1)   //若该位=1，则当前位为1的个数为该位右边的数字组成的数+1    
47.             count+=n%weight+1;  
48.           
49.         a=10*a+weight;  //an=10 * a(n-1) + 10^(m-1), m为位数    
50.         weight*=10;   //这里a和weight是上面推导对应的数
51.        
52.         temp/=10;  
53.     }  
54.     return count;  
55. }  
56.   
57. //显示菜单    
58. void show_menu()  
59. {  
60.     printf("---------------------------------------------/n");  
61.     printf("input command to test the program/n");  
62.     printf("   i or I : input n to test/n");  
63.     printf("   g or G : get n to enable f(n)=n/n");  
64.     printf("   q or Q : quit/n");  
65.     printf("---------------------------------------------/n");  
66.     printf("$ input command >");  
67. }  
68.   
69. void main()  
70. {  
71.     char sinput[10];  
72.     long long n;  
73.   
74.     show_menu();  
75.   
76.     scanf("%s",sinput);  
77.     while(stricmp(sinput,"q")!=0)  
78.     {  
79.         int t=0;  
80.         long long count=0;  
81.         if(stricmp(sinput,"i")==0)  
82.         {  
83.             printf("  please input an integer:");  
84.             scanf("%lld",&n);  
85.   
86.             count=0;  
87.             CalculationTimes obj;  
88.             t=GetTickCount();  
89.             count=obj.GetTimes(n);  
90.             t=GetTickCount()-t;  
91.             printf("/n  count=%lld    time=%d/n/n",count,t);  
92.         }  
93.         else if(stricmp(sinput,"g")==0)  
94.         {  
95.             CalculationTimes obj;  
96.             n=2;  
97.             t=GetTickCount();  
98.             while(1)  
99.             {  
100.                 count=obj.GetTimes(n);  
101.                 if(count==n)  
102.                     break;  
103.                 n++;  
104.             }  
105.             t=GetTickCount()-t;  
106.             printf("/n  f(n)=n=%lld    time=%d/n/n",n,t);  
107.         }  
108.   
109.   
110.         //输入命令    
111.         printf("$ input command >");  
112.         scanf("%s",sinput);  
113.     }  
114. }  

  

6. 运行结果

 

 

由算法本身和程序运行结果来看，本算法的效率非常高，将问题的解法转化为纯粹的数学计算，只需要简单的计算即可得到结果。