display | more...
Answer to old chestnut: house number problems

The answer is 20. He needs ten 9s for the ones digit in 9, 19, 29, ..., 99, and ten more 9s for the tens digit in 90, 91, 92, ... 99.

In general, this problem can be solved by the following shortcut:

In order to count all the occurrences of digit X in 0 to 10N-1, consider all the numbers with leading zeroes, so that each is N digits long. There are two key observations here. First, note that every possible combination of N consecutive digits is now represented. Second, note that each digit occurs equally often in such a set. The total number of digits is N x 10N, and since each occurs equally often, each occurs N x 10N-1 times.

Now, if you want to count zeroes, you need to subtract the number of leading zeroes. This is (N-1) x 10 (assuming the number zero is represented with a single zero) + (N-2) x 90 + (N-3) x 900 + ... + 1 x 9 x 10N-2.

These problems usually use intervals of 1 to 100 or so, rather than 0 to 99. As long as you aren't asked to count the number of ones or zeroes, there is no difference, and if you are, it's easy to take that into account at the end.

Log in or register to write something here or to contact authors.