## Interview Question

Investment Analyst Interview

-

# 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.

2

besmart is close. I cheated by coding it up and 199981 is the first one after the trivial case.

Anonymous on

0

Wouldn't that merely occur @ n = 1?

Anonymous on

0

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)

Anonymous on

0

f(0) = 0, if we are dealing with real numbers, zero counts

Anonymous on

0

In working it out in a very painful way, I got 199,991.

Anonymous on

0

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.

Anonymous on

0

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!

besmart on