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

The roadmap to compute all fixed points of f(x) is to start from boundaries 1, or 10^10, and keep acting f on it. If x is a boundary point, first compare x and f(x) to see whether we should generate the series using f or f inverse. Once we know which one to use, then keep doing that until we get a fixed point. Then start from the next integer again.

In order to do these, we need a few functions:
1. function f:

java 代码

1. private long numOfOnes(long x)
2. {
3.     // recursion stops
4.     if (x <= 0) return 0;
5.     if (x == 1) return 1;
7.     int powerk = 0;
8.     long tenPowers = 1;
9.     long leadingDigit = x;
10.     while (leadingDigit >= 10)
11.     {
12.         leadingDigit /= 10;
13.         powerk++;
14.         tenPowers *= 10;
15.     }
17.     long reminder = x - leadingDigit * tenPowers;
18.     if (leadingDigit == 1)
19.     {
20.         return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);
21.     }
22.     else
23.     {
24.         return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);
25.     }
26. }

This is basically a direct translate of the formula (A) and (B) in Lemma 4.

2. inverse of f:
Obviously the next one is f inverse. Since f is not single valued, we have to have a better definition on the inverse. We define the inverse of f for a given y as the smallest x such that x < y <= f(x), so we could step as far as possible.

java 代码

1. public long inverseFunc(long y)
2. {
3.     // recursion default.
4.     if (y <= 0) return 0;
5.     if (y == 1) return 1;
6.     if (y == 2) return 10;
8.     // check whether y is in 1's range
9.     int m = isInOneRange(y);
10.     if (m != -1)
11.     {
12.         long tmp = y - (m + 1) * power(10, m) - 1;
13.         long inc = findRoot(tmp);
14.         return power(10, m + 1) + inc;
15.     }
16.     else
17.     {
18.         int k = numOfDigits(y) - 1;
19.         long tmp = y - power(10, k);
20.         long ak = tmp / (k * power(10, k - 1));
21.         if (ak > 9) ak = 9; // leave the rest to the recursion
22.         long remainder = tmp - ak * k * power(10, k - 1);
23.         long xRemainder = inverseFunc(remainder);
24.         return ak * power(10, k) + xRemainder;
25.     }
26. }

The tricky part here is to figure out the power k. Here in order to know whether we should use formula (A) or (B), we need to check whether the to-be-found x has leading 1. So the helper function is

java 代码

1. private int isInOneRange(long y)
2. {
3. // This is to check whether the func value is between the function
   
4. // values of 10^n and 2*10^n.
6. // this can be done faster since it's sorted, but again I am lazy
7. int k=-1;
8. for (int i=0; i<9; i++)
9. {
10. if (y <= y2[i])
11. {
12. k = i;
13. break; // first smaller, break out
14. }
15. }
17. if (k==-1) return -1;
19. if (y >= y1[k]) return k;
20. else return -1;
21. }

where we define the following

java 代码

1. long[] x1 = new long[9];
2. long[] x2 = new long[9];
3. long[] y1 = new long[9];
4. long[] y2 = new long[9];
6. for (int i=1; i<10; i++)
7. {
8. x1[i-1] = power(10, i);
9. x2[i-1] = 2 * x1[i-1] - 1;
10. y1[i-1] = numOfOnes(x1[i-1]);
11. y2[i-1] = numOfOnes(x2[i-1]);
12. }
14. If we print out them:
16. x range=[10, 19] y range=[2, 12]
17. x range=[100, 199] y range=[21, 140]
18. x range=[1000, 1999] y range=[301, 1600]
19. x range=[10000, 19999] y range=[4001, 18000]
20. x range=[100000, 199999] y range=[50001, 200000]
21. x range=[1000000, 1999999] y range=[600001, 2200000]
22. x range=[10000000, 19999999] y range=[7000001, 24000000]
23. x range=[100000000, 199999999] y range=[80000001, 260000000]
24. x range=[1000000000, 1999999999] y range=[900000001, 2800000000]

The other missing piece is the function foundRoot(). This is used in formula (A), which can be simplified in the form x + f(x) = y, with unknown x. We need a function to find the root x.

java 代码

1. public long findRoot(long y)
2. {
3. // find a root for x + f(x) = y, where f is the number of one's function
   
4. // in the above.
5. // we need a x such that x + f(x)>=y, the largest x.
6. // Note that x + f(x) is a mononically increasing function.
7. long x0 = 0;
8. long x1 = y;
9. long x;
10. while (x1 - x0 > 1)
11. {
12. x = x0 + (x1 - x0) / 2;
13. long func = numOfOnes(x) + x;
14. if (func == y) return x;
15. if (func < y)
16. {
17. x0 = x;
18. }
19. else
20. {
21. x1 = x;
22. }
23. }
25. if (x0 + numOfOnes(x0) == y) return x0;
26. else return x1;
27. }

Two other small functions are:

java 代码

1. private static int numOfDigits(long x)
2. {
3. int i = 0;
4. while (x > 0)
5. {
6. x /= 10;
7. i++;
8. }
10. return i;
11. }

which computes the number of 1's in x, and

java 代码

1. private static long power(long base, int power)
2. {
3. long ret = 1;
4. for (int i=1; i<=power; i++) ret *= base;
5. return ret;
6. }

which computes the power for the performance reason. With all of these in places, the only thing left is a "conductor" method:

java 代码

1. public void countDigitOne()
2. {
3. long begin = System.currentTimeMillis();
5. long loop = 10000000000L;
7. int iterationTimes = 1;
8. while (loop > 0 && iterationTimes < ITERATION_LIMIT)
9. {
10. long func = numOfOnes(loop);
11. if (func == loop)
12. {
13. System.out.println("-----> found a fixed point: x=" + loop);
14. // now skip this one and keep going for the next one.
15. loop--;
16. }
17. else
18. {
19. if (func < loop) // we force this to go to the left.
20. {
21. loop = func;
22. }
23. else // func > loop
24. {
25. func = inverseFunc(loop);
26. if (func < loop && numOfOnes(func) >= loop)
27. {
28. loop = func;
29. }
30. else
31. {
32. loop --; // if we can't find one, just decrement it.
33. }
34. }
35. }
37. iterationTimes++;
38. }
40. System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");
41. System.out.println("It takes " + iterationTimes + " iterations");
42. }

The result is:

-----> found a fixed point: x=1111111110
-----> found a fixed point: x=535200001
-----> found a fixed point: x=535200000
-----> found a fixed point: x=535199990
-----> found a fixed point: x=535199989
-----> found a fixed point: x=535199988
-----> found a fixed point: x=535199987
-----> found a fixed point: x=535199986
-----> found a fixed point: x=535199985
-----> found a fixed point: x=535199984
-----> found a fixed point: x=535199983
-----> found a fixed point: x=535199982
-----> found a fixed point: x=535199981
-----> found a fixed point: x=535000001
-----> found a fixed point: x=535000000
-----> found a fixed point: x=513199998
-----> found a fixed point: x=502600001
-----> found a fixed point: x=502600000
-----> found a fixed point: x=501599990
-----> found a fixed point: x=501599989
-----> found a fixed point: x=501599988
-----> found a fixed point: x=501599987
-----> found a fixed point: x=501599986
-----> found a fixed point: x=501599985
-----> found a fixed point: x=501599984
-----> found a fixed point: x=501599983
-----> found a fixed point: x=501599982
-----> found a fixed point: x=501599981
-----> found a fixed point: x=500200001
-----> found a fixed point: x=500200000
-----> found a fixed point: x=500199990
-----> found a fixed point: x=500199989
-----> found a fixed point: x=500199988
-----> found a fixed point: x=500199987
-----> found a fixed point: x=500199986
-----> found a fixed point: x=500199985
-----> found a fixed point: x=500199984
-----> found a fixed point: x=500199983
-----> found a fixed point: x=500199982
-----> found a fixed point: x=500199981
-----> found a fixed point: x=500000001
-----> found a fixed point: x=500000000
-----> found a fixed point: x=117463825
-----> found a fixed point: x=35200001
-----> found a fixed point: x=35200000
-----> found a fixed point: x=35199990
-----> found a fixed point: x=35199989
-----> found a fixed point: x=35199988
-----> found a fixed point: x=35199987
-----> found a fixed point: x=35199986
-----> found a fixed point: x=35199985
-----> found a fixed point: x=35199984
-----> found a fixed point: x=35199983
-----> found a fixed point: x=35199982
-----> found a fixed point: x=35199981
-----> found a fixed point: x=35000001
-----> found a fixed point: x=35000000
-----> found a fixed point: x=13199998
-----> found a fixed point: x=2600001
-----> found a fixed point: x=2600000
-----> found a fixed point: x=1599990
-----> found a fixed point: x=1599989
-----> found a fixed point: x=1599988
-----> found a fixed point: x=1599987
-----> found a fixed point: x=1599986
-----> found a fixed point: x=1599985
-----> found a fixed point: x=1599984
-----> found a fixed point: x=1599983
-----> found a fixed point: x=1599982
-----> found a fixed point: x=1599981
-----> found a fixed point: x=200001
-----> found a fixed point: x=200000
-----> found a fixed point: x=199990
-----> found a fixed point: x=199989
-----> found a fixed point: x=199988
-----> found a fixed point: x=199987
-----> found a fixed point: x=199986
-----> found a fixed point: x=199985
-----> found a fixed point: x=199984
-----> found a fixed point: x=199983
-----> found a fixed point: x=199982
-----> found a fixed point: x=199981
-----> found a fixed point: x=1
It takes 62 milli
It takes 1139 iterations.

This is a typical fixed point problem, start from some arbitrary number and keep acting f on it. Several outputs of the series are:
1. It goes to infinity.
2. It goes to some fixed point.
3. It keeps bouncing back and forth(going nowhere).

Two types of fixed points are attractors and opposite attractors. Attractors are attracting nearby points, i.e., if we start from some point "close" enough to the attractor, the series will converge to the attractor. Opposite attractor is just the opposite, the series will go away from the opposite attractor.