A Google's Interview Question - GLAT #20 series 4 博客分类： algorithms GoogleF#RESTGoUP

The entire class is as follows:

java 代码

 

1. /** 
2. * GOOGLE GLAT question #20: 
3. * Consider a function which, for a given whole number n, returns the number 
4. * of ones required when writing out all numbers between 0 and n. For example, 
5. * f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? 
6. */  
7. public class CountOnesUseIteration  
8. {  
9.     // Implementation notes:  
10.     // There are various places we can optimize the code, however I don't  
11.     // feel we need to do so since the implementation is fast enough.  
12.   
13.     private static final int ITERATION_LIMIT = 10000;  
14.   
15.     // This is used to check whether any given func value is between the  
16.     // function values of 10^n and 2*10^n so that we know the corresponding  
17.     // number starts with 1 or not, this fact will determine which formula  
18.     // to use for reverse iteration.  
19.     long[] x1 = new long[9];  
20.     long[] x2 = new long[9];  
21.     long[] y1 = new long[9];  
22.     long[] y2 = new long[9];  
23.   
24.     public CountOnesUseIteration()  
25.     {  
26.         for (int i=1; i<10; i++)  
27.         {  
28.             x1[i-1] = power(10, i);  
29.             x2[i-1] = 2 * x1[i-1] - 1;  
30.             y1[i-1] = numOfOnes(x1[i-1]);  
31.             y2[i-1] = numOfOnes(x2[i-1]);  
32.         }  
33.     }  
34.   
35.     public void countDigitOne()  
36.     {  
37.         long begin = System.currentTimeMillis();  
38.   
39.         long loop = 10000000000L;  
40.   
41.         int iterationTimes = 1;  
42.         while (loop > 0 && iterationTimes < ITERATION_LIMIT)  
43.         {  
44.             long func = numOfOnes(loop);  
45.             if (func == loop)  
46.             {  
47.                 System.out.println("-----> found a fixed point: x=" + loop);  
48.                 // now skip this one and keep going for the next one.  
49.                 loop--;  
50.             }  
51.             else  
52.             {  
53.                 if (func < loop) // we force this to go to the left.  
54.                 {  
55.                     loop = func;  
56.                 }  
57.                 else // func > loop  
58.                 {  
59.                     func = inverseFunc(loop);  
60.                     if (func < loop && numOfOnes(func) >= loop)  
61.                     {  
62.                         loop = func;  
63.                     }  
64.                     else  
65.                     {  
66.                         loop --; // if we can't find one, just decrement it.  
67.                     }  
68.                 }  
69.             }  
70.   
71.             iterationTimes++;  
72.         }  
73.   
74.         System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");  
75.         System.out.println("It takes " + iterationTimes + " iterations");  
76.     }  
77.   
78.     // function value  
79.     private long numOfOnes(long x)  
80.     {  
81.         // recursion stops  
82.         if (x <= 0) return 0;  
83.         if (x == 1) return 1;  
84.   
85.         int powerk = 0;  
86.         long tenPowers = 1;  
87.         long leadingDigit = x;  
88.         while (leadingDigit >= 10)  
89.         {  
90.             leadingDigit /= 10;  
91.             powerk++;  
92.             tenPowers *= 10;  
93.         }  
94.   
95.         long reminder = x - leadingDigit * tenPowers;  
96.         if (leadingDigit == 1)  
97.         {  
98.             return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);  
99.         }  
100.         else  
101.         {  
102.             return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);  
103.         }  
104.     }  
105.   
106.     // kind of inverse function value  
107.     public long inverseFunc(long y)  
108.     {  
109.         // we are moving backward to find a x such that x < y <= f(x) and keep x as small as possible.  
110.   
111.         // recursion default.  
112.         if (y <= 0) return 0;  
113.         if (y == 1) return 1;  
114.         if (y == 2) return 10;  
115.   
116.         // check whether y is in 1's range  
117.         int m = isInOneRange(y);  
118.         if (m != -1)  
119.         {  
120.             long tmp = y - (m + 1) * power(10, m) - 1;  
121.             long inc = findRoot(tmp);  
122.             return power(10, m + 1) + inc;  
123.         }  
124.         else  
125.         {  
126.             int k = numOfDigits(y) - 1;  
127.             long tmp = y - power(10, k);  
128.             long ak = tmp / (k * power(10, k - 1));  
129.             if (ak > 9) ak = 9; // leave the rest to the recursion  
130.             long remainder = tmp - ak * k * power(10, k - 1);  
131.             long xRemainder = inverseFunc(remainder);  
132.             return ak * power(10, k) + xRemainder;  
133.         }  
134.     }  
135.   
136.     private int isInOneRange(long y)  
137.     {  
138.         // This is to check whether the func value is between the function values of 10^n and 2*10^n.  
139.   
140.         // this can be done faster since it's sorted, but again I am lazy  
141.         int k=-1;  
142.         for (int i=0; i<9; i++)  
143.         {  
144.             if (y <= y2[i])  
145.             {  
146.                 k = i;  
147.                 break; // first smaller, break out  
148.             }  
149.         }  
150.   
151.         if (k==-1) return -1;  
152.   
153.         if (y >= y1[k]) return k;  
154.         else return -1;  
155.     }  
156.   
157.     private static int numOfDigits(long x)  
158.     {  
159.         int i = 0;  
160.         while (x > 0)  
161.         {  
162.             x /= 10;  
163.             i++;  
164.         }  
165.   
166.         return i;  
167.     }  
168.   
169.     private static long power(long base, int power)  
170.     {  
171.         long ret = 1;  
172.         for (int i=1; i<=power; i++) ret *= base;  
173.         return ret;  
174.     }  
175.   
176.     public long findRoot(long y)  
177.     {  
178.         // find a root for  x + f(x) = y, where f is the number of one's function in the above.  
179.         // we need a x such that x + f(x)>=y, the least x.  
180.         // Note that x + f(x) is a mononically increasing function.  
181.         long x0 = 0;  
182.         long x1 = y;  
183.         long x;  
184.         while (x1 - x0 > 1)  
185.         {  
186.             x = x0 + (x1 - x0) / 2;  
187.             long func = numOfOnes(x) + x;  
188.             if (func == y) return x;  
189.             if (func < y)  
190.             {  
191.                 x0 = x;  
192.             }  
193.             else  
194.             {  
195.                 x1 = x;  
196.             }  
197.         }  
198.   
199.         if (x0 + numOfOnes(x0) == y) return x0;  
200.         else return x1;  
201.     }  
202. }  

There are possible places where we can speed up further, but hardly worth it.