GLAT Google Lab Aptitude Test
GLAT Question 17: "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?"
Naive implementation of f( ) may go like this one liner:
def f n (1..n).inject(0) {|s, i| s + i.to_s.gsub(/[^1]/, '').length} end p f(13) # => 6
Likewise we can solve the problem by this:
s = 1 i = 1 begin i += 1 s += i.to_s.gsub(/[^1]/, '').length end until i == s puts i # => 199981
That's fine; but, do we really need Ruby?
# f(10^k - 1) = k*10^(k-1) p f(9), f(99), f(999), f(9999) # => 1, 20, 300, 4000, ..
This sequence never achieves f(n) = n, because n = 10^k - 1 > k*10^(k-1).
But take a look at an area where "1"s are rich, that is, 10^k..2*10^k.
# f(2*10^n-1) = 2*f(10^n - 1) + 10^n = (2*n + 10)*10^(n-1) p f(19),f(199),f(1999),f(19999) # => 12, 140, 1600, 18000, ..
In case n == 5, f(199,999) = 2*10^5
So, luckily we can hand calculate and step back a few:
f(199,981) = f(199,999) - 19 = 199,981 !