A Google's Interview Question - GLAT #20 series 2 博客分类： algorithms GoogleF#UP
程序员文章站
2024-03-07 11:55:21
...
Now, we can deduct the recursion formula on digits
Lemma 4
Let
n = a_k * 10^k + a_(k-1) * 10^(k-1) + ....... + a_1 * 10 + a_0
denote the base 10 expansion, then
when a_k = 1
(A) f(n) = f(n - 10^k) + (n - 10^k) + f(10^k) = f(n - 10^k) + (n - 10^k) + k * 10^(k-1) + 1
and when a_k > 1
(B) f(n) = f(n - a_k * 10^k) + f(a_k * 10^k) = f(n - a_k * 10^k) + a_k * k * 10^(k-1) + 10^k
In A, since a_k = 1, n - 10^k is really the number without the leading digit. So the first term is the 1's above 10^k without leading 1's. The second term is the leading 1's above 10^k. The 3rd term is the 1's from the numbers up to 10^k.
In B, the first term is the 1's above a_k * 10^k and the second term is the 1's below a_k * 10^k.
Further more, from (A)
from (B)
so in either case, when k >= 10, f(n) > n. This means the upper bound for n such that f(n) = n is 10^10.
From here on, if we want to find all integers n such that f(n) = n, then looping through 1 to 10^10 is still a long task, could take several hours. So we still need to dig some information from the function f(n) to narrow down our search.
Lemma 5.
All positive integers are divided by the fixed points of f(n) such that in each interval, we either have f(x) > x or f(x) < x throughout the entire interval.
Obviously, f(n) is a non decreasing function, i.e., if x > y, then f(x) >= f(y). So for any given positive integer n, if f(n) > n, then f(f(n)) >= f(n) > n. This means n, f(n), f(f(n)), ...... form an increasing series. Furthermore, there can't exist any fixed point m between any two distinct adjacent points in this series such that f(m) = m. Otherwise, if exists y such that n < m < f(n), then act f on them would get f(n) <= f(m) <= f(f(m)). This leads f(n) <= f(m) = m, contradicts to where we start m < f(n) <= m. This means the entire series must lie between fixed points.
If there are two points x and y in such an internal(i.e., no more fixed points besides the end points), such that f(x) > x, and f(y) < y. Then we will show there must be a fixed point between x and y.
If x < y, then this means x-series and y-series are merging in finite steps. Since all y-series are upper bounder, x-series has to stop before reaching y-series, there must be a number x_0 in x-series such that x_0 = f(x_0).
if x > y, then this means they are diverging away to two endpoints. If we keep bisect x and y, we end up the case where there is an integer z such that f(z) <= z < z + 1 <= f(z + 1). If both z and z+1 are not fixed points, then f inverse on z would be >= z+1.
if z_0 is one of the inverse, then
z < z + 1 < z_0 and f(z_0) = z.
Then acting f on this ends up with
f(z) <= f(z + 1) <= f(z_0) = z
This contradicts with the fact f(z + 1) >= z + 1 > z.
So there must be at least a fixed point in the middle.
Lemma 5 is the beauty of this function.
Lemma 4
Let
n = a_k * 10^k + a_(k-1) * 10^(k-1) + ....... + a_1 * 10 + a_0
denote the base 10 expansion, then
when a_k = 1
(A) f(n) = f(n - 10^k) + (n - 10^k) + f(10^k) = f(n - 10^k) + (n - 10^k) + k * 10^(k-1) + 1
and when a_k > 1
(B) f(n) = f(n - a_k * 10^k) + f(a_k * 10^k) = f(n - a_k * 10^k) + a_k * k * 10^(k-1) + 10^k
In A, since a_k = 1, n - 10^k is really the number without the leading digit. So the first term is the 1's above 10^k without leading 1's. The second term is the leading 1's above 10^k. The 3rd term is the 1's from the numbers up to 10^k.
In B, the first term is the 1's above a_k * 10^k and the second term is the 1's below a_k * 10^k.
Further more, from (A)
f(n) > (n - 10^k) + k * 10^(k-1) (ignore the f(n-10^k) and 1 terms)
= n + (k - 10) * 10 ^(k-1)
from (B)
f(n) > a_k * k * 10^(k-1) + 10^k (ignore the first term)
> a_k * k * 10^(k-1) + n - a_k * 10 ^k
= n + a_k * (k - 10) * 10^(k-1)
so in either case, when k >= 10, f(n) > n. This means the upper bound for n such that f(n) = n is 10^10.
From here on, if we want to find all integers n such that f(n) = n, then looping through 1 to 10^10 is still a long task, could take several hours. So we still need to dig some information from the function f(n) to narrow down our search.
Lemma 5.
All positive integers are divided by the fixed points of f(n) such that in each interval, we either have f(x) > x or f(x) < x throughout the entire interval.
Obviously, f(n) is a non decreasing function, i.e., if x > y, then f(x) >= f(y). So for any given positive integer n, if f(n) > n, then f(f(n)) >= f(n) > n. This means n, f(n), f(f(n)), ...... form an increasing series. Furthermore, there can't exist any fixed point m between any two distinct adjacent points in this series such that f(m) = m. Otherwise, if exists y such that n < m < f(n), then act f on them would get f(n) <= f(m) <= f(f(m)). This leads f(n) <= f(m) = m, contradicts to where we start m < f(n) <= m. This means the entire series must lie between fixed points.
If there are two points x and y in such an internal(i.e., no more fixed points besides the end points), such that f(x) > x, and f(y) < y. Then we will show there must be a fixed point between x and y.
If x < y, then this means x-series and y-series are merging in finite steps. Since all y-series are upper bounder, x-series has to stop before reaching y-series, there must be a number x_0 in x-series such that x_0 = f(x_0).
if x > y, then this means they are diverging away to two endpoints. If we keep bisect x and y, we end up the case where there is an integer z such that f(z) <= z < z + 1 <= f(z + 1). If both z and z+1 are not fixed points, then f inverse on z would be >= z+1.
if z_0 is one of the inverse, then
z < z + 1 < z_0 and f(z_0) = z.
Then acting f on this ends up with
f(z) <= f(z + 1) <= f(z_0) = z
This contradicts with the fact f(z + 1) >= z + 1 > z.
So there must be at least a fixed point in the middle.
Lemma 5 is the beauty of this function.