学步园

正整数中数字1的计数问题（上）

原题出自Google的一道比较老的面试题：

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?

本实现没有利用可能存在的数学公式，只考虑相邻两个数得变化规律，因此运行效率并不理想。如何计算单个值f(n)的快速算法，请参考我的另一篇文章。

public class OnesCount {<br /> /**<br /> * Problem:<br /> * Consider a function which, for a given whole number n,<br /> * returns the number of ones required when writing out all<br /> * numbers between 0 and n.<br /> * For example, f(13)=6. Notice that f(1)=1.<br /> * What is the next largest n such that f(n)=n?<br /> *<br /> *<br /> * Print the next i for f(i)=i; stop when we reach n and return f(n).<br /> * n: long integer<br /> */<br /> public static long solve(long n){<br /> //the number of digits in n<br /> int digitsCount=1;<br /> long tmp = n;<br /> while((tmp /= 10) >0)<br /> digitsCount++; </p> <p> int prevDigitIndex = digitsCount - 2;<br /> int leastDigitIndex = digitsCount - 1;<br /> if(prevDigitIndex<0){ //one-digit input<br /> System.out.format("n=%d=f(n)%n",0);<br /> if(n>0)<br /> System.out.format("n=%d=f(n)%n",1);</p> <p> int count = 0;<br /> if(n<=1){ //0 and 1<br /> count = (int)n;<br /> }else{<br /> count = 1;<br /> }<br /> return count;<br /> }</p> <p> //initialized to zero<br /> byte[] digits = new byte[digitsCount];<br /> long totalOnesCount = 0;<br /> int nextOnesCount = 0;<br /> int k=0; //the least significant digit: from 0 to 9 </p> <p> for(long i=0;i<=n;i++){<br /> int currOnesCount = nextOnesCount;<br /> if(k==0){ //x0 - > x1<br /> digits[leastDigitIndex] = 1;<br /> nextOnesCount = currOnesCount + 1;<br /> }else if(k==1){ //x1 - > x2<br /> digits[leastDigitIndex] = 2;<br /> nextOnesCount = currOnesCount - 1;<br /> }else if(k==9){ //x9 -> ...<br /> byte nextDigit = digits[prevDigitIndex]; //x<br /> switch(nextDigit){<br /> case 0: //09 -> 10<br /> digits[prevDigitIndex] = 1;<br /> digits[leastDigitIndex] = 0;<br /> nextOnesCount = currOnesCount + 1;<br /> break;<br /> case 1: //19 -> 20<br /> digits[prevDigitIndex] = 2;<br /> digits[leastDigitIndex] = 0;<br /> nextOnesCount = currOnesCount - 1;<br /> break;<br /> case 9: //99<br /> int tmpIndex = prevDigitIndex;<br /> digits[leastDigitIndex] = 0;<br /> digits[prevDigitIndex] = 0;<br /> while((--tmpIndex)>=0 && digits[tmpIndex]==9){<br /> digits[tmpIndex] = 0;<br /> }</p> <p> if(tmpIndex>=0){<br /> int d = (digits[tmpIndex]+=1);<br /> if(d==2){ //199 -> 200<br /> nextOnesCount = currOnesCount - 1;<br /> }else if(d==1){ //099 -> 100<br /> nextOnesCount = currOnesCount + 1;<br /> }else{ //399 -> 400<br /> nextOnesCount = currOnesCount;<br /> }<br /> }<br /> break;<br /> default: //29 ~ 89 -> 30 ~ 90<br /> digits[prevDigitIndex] += 1;<br /> digits[leastDigitIndex] = 0;<br /> nextOnesCount = currOnesCount;<br /> break;<br /> }<br /> }else{ //x2 ~ x8 -> x3 ~ x9<br /> digits[leastDigitIndex] += 1;<br /> nextOnesCount = currOnesCount;<br /> }<br /> k = digits[leastDigitIndex];</p> <p> totalOnesCount += currOnesCount;<br /> if(i==totalOnesCount){<br /> System.out.format("n=%d=f(n)%n",i);<br /> }<br /> }<br /> return totalOnesCount;<br /> }</p> <p> public static void main(String[] args) {<br /> long n=1111111110;<br /> //long n=1111111110;<br /> //long n=1036;</p> <p> long start = System.currentTimeMillis();</p> <p> long ones = OnesCount.solve(n);<br /> System.out.format("f(%d) = %d%n",n,ones);</p> <p> long end = System.currentTimeMillis();</p> <p> double timeElapsed = (end-start)/1000.0;<br /> System.out.format("Time elapsed(sec): %.3f%n", timeElapsed);<br /> }<br /> }<br />

测试结果（Pentium M 1.4GHz, 512M内存）：

n=0=f(n)
n=1=f(n)
n=199981=f(n)
n=199982=f(n)
n=199983=f(n)
n=199984=f(n)
n=199985=f(n)
n=199986=f(n)
n=199987=f(n)
n=199988=f(n)
n=199989=f(n)
n=199990=f(n)
n=200000=f(n)
n=200001=f(n)
n=1599981=f(n)
n=1599982=f(n)
n=1599983=f(n)
n=1599984=f(n)
n=1599985=f(n)
n=1599986=f(n)
n=1599987=f(n)
n=1599988=f(n)
n=1599989=f(n)
n=1599990=f(n)
n=2600000=f(n)
n=2600001=f(n)
n=13199998=f(n)
n=35000000=f(n)
n=35000001=f(n)
n=35199981=f(n)
n=35199982=f(n)
n=35199983=f(n)
n=35199984=f(n)
n=35199985=f(n)
n=35199986=f(n)
n=35199987=f(n)
n=35199988=f(n)
n=35199989=f(n)
n=35199990=f(n)
n=35200000=f(n)
n=35200001=f(n)
n=117463825=f(n)
n=500000000=f(n)
n=500000001=f(n)
n=500199981=f(n)
n=500199982=f(n)
n=500199983=f(n)
n=500199984=f(n)
n=500199985=f(n)
n=500199986=f(n)
n=500199987=f(n)
n=500199988=f(n)
n=500199989=f(n)
n=500199990=f(n)
n=500200000=f(n)
n=500200001=f(n)
n=501599981=f(n)
n=501599982=f(n)
n=501599983=f(n)
n=501599984=f(n)
n=501599985=f(n)
n=501599986=f(n)
n=501599987=f(n)
n=501599988=f(n)
n=501599989=f(n)
n=501599990=f(n)
n=502600000=f(n)
n=502600001=f(n)
n=513199998=f(n)
n=535000000=f(n)
n=535000001=f(n)
n=535199981=f(n)
n=535199982=f(n)
n=535199983=f(n)
n=535199984=f(n)
n=535199985=f(n)
n=535199986=f(n)
n=535199987=f(n)
n=535199988=f(n)
n=535199989=f(n)
n=535199990=f(n)
n=535200000=f(n)
n=535200001=f(n)
n=1111111110=f(n)
f(1111111110) = 1111111110
Time elapsed(sec): 32.657