A Google's Interview Question - GLAT #20 series 1 博客分类： algorithms GoogleF#REST

Question:

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's the next largest n such that f(n) = n?

As always, start with simple cases:

f(1) = 1,

f(2) = 1,

.......

f(9) = 1,

f(10) = 2, since 10 starts with 1, which we need to add.

f(11) = 4, since there are two 1's in 11 that we need to add.

f(12) = 5,

f(13) = 6,

....

f(19) = 12,

So between 12 and 19, we need to add 1 for each number because the second digit is one. Moreover, between 10 and 19, we add 10 1's from the second digit and one 1 from the last digit.

f(20) = 12,

f(21) = 13,

f(22) = 13,

.....

f(29) = 13,

So between 20 and 29, there is only one 1 from the last digit. Moreover, this is true for all subsequent intervals 30-39, 40-49, ......, 90-99. Consequently,

f(99) =    1 (between 1 and 9)

         + 1 (from the last digit in 11)

         + 10 (from the second digit in 10, 11, ......19)

         + 1 (in 31)

         + 1 (in 41)

         + ............

         + 1 (in 91)

         = 10 (from second digit) + 10 (from first digit)

         = 20.

In general, we can deduct

Lemma 1.

f(10^k - 1) = k * 10^(k-1)

for example,

f(9) = 1

f(99) = 2 * 10 = 20,

......

This is deducted from counting 1's in each digit for all number from 1 to 10^k -1, there are 10^(k-1) 1's in each of k digits.  Actually, 1 appears in the last digit exactly once in every 10 consecutive numbers(like in 1, 11, 21, 31, ....) and so we have 10^k/10=10^(k-1) 1's contributed from last digit. Similarly, 1 appears 10 times in the second digit from last for every 100 consecutive numbers(like in 10-19, 110-119, 210-219, ...) and so we have 10 * (10^k/100) = 10^(k-1).      

From this lemma, we can deduct

Lemma 2.

f(10^k) = k *10^(k-1) + 1.

The extra 1 is from the leading 1 in 10^k.

Recall the above process counting 1's between 10-99, we can deduct

Lemma 3.

f(m * 10^k) = m * f(10^k - 1) + 10^k = m * k * 10^(k - 1) + 10^k, for 1 < m < 9.

The second equality is using Lemma 1. This is just extending Lemma 1 to the cases where leading digits are bigger than 1.

The counting is just done by breaking the range between 1 and m * 10^k to two ranges, one is from 10^k to 2 * 10^k for leading 1's, and the rest. For example, f(5000) is breaking into 1-999, 1000-1999, 2000-2999, 3000-3999, and 4000-4999. Ignore the leading 1's, each range contributes f(10^k - 1). The leading 1's can only come from the second range 1000-1999, which has exactly 10^k leading 1's.