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 !