DC Energy Interview Question: f(n) is a function counting a... | Glassdoor

Interview Question

Investment Analyst Interview(Student Candidate) Washington, DC

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.

0

Wouldn't that merely occur @ n = 1?

Anonymous on May 24, 2010
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 May 25, 2010
0

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

Anonymous on Aug 12, 2010
0

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

Anonymous on Oct 3, 2010
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 Sep 29, 2011
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 Sep 1, 2012
2

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

Anonymous on Sep 9, 2012