关于一道面试题

时间:2021-05-12 17:07:23
有这样一个函数,对于任意整数n,都能返回写出0到n之间出现“1”的个数。例如,f(13)=6。请注意f(1)=1,那么下一个能实现f(n)=n的最大数字是什么?

f(10) = f(1) + 1
f(100) = f(9) * 10 + 100/10 + 1
f(1000) = f(99) * 10 + 1000/10 + 1
f(10000) = f(999) * 10 + 10000/10 + 1
f(100000) = f(9999) * 10 + 100000/10 + 1
f(200000) = f(100000) + f(9999) + 100000/10 = 200000

其中 f(1000 ) = f(999) +1以此类推