DC Energy interview question
f(n) is a function counting all the ones that show up in 1, 2, 3, ..., n. so f(1)=1, f(10)=2, f(11)=4 etc. When is the first time f(n)=n.
Interview Answers
besmart is close.
I cheated by coding it up and 199981 is the first one after the trivial case.
Wouldn't that merely occur @ n = 1?
sorry, forgot to mention other than the trivial case at n=1. the answer should be around 20000 if i recall correctly (think its 19991 but need double check on that)
f(0) = 0, if we are dealing with real numbers, zero counts
In working it out in a very painful way, I got 199,991.
f(9) = 1.
f(99) = 1 * 10 + 10 = 20.
f(999) = 20 * 10 + 100 = 300. (the 2-digit sequence occurs 10 times, and then you need to add 100 for all the numbers like "1xx")
Then we can think about f(20) or f(200) since a lot of the 1's occur in the 100's)
f(20) = 1 * 2 + 10 = 12
f(200) = 20 * 2 + 100 = 140
f(2000) = 300 * 2 + 1000 = 1600
f(20000) = 4000 * 2 + 10000 = 18000
f(200000) = 200000.
f(199999) = 200000.
f(199991) = 199992.
n decreases faster than f(n), so I think 200000 is our answer.
I think the above is very close but one tiny step away.
f(199999)=200000. Correct.
But from here, if n decrease by 1 each time, f(n) decreases by 1 as well until n hits 199991, which contains two 1s, f(199991)=199992. So,
f(199990)=199990.
Bingo!