Skip to content
Advertisement

How do I count numbers that contain one digit, but not another?

I recently came across an interview question which although had an immediately obvious solution, I struggled to find a more efficient one.

The actual question involved counting numbers from a to b (up to 2^64) which satisfied having either the digit 6 or 8, but not both. They called it a ‘lucky number’. So for example:

126 - lucky
88 - lucky
856 - not lucky

The obvious thought was to brute force it by testing each number between a and b as a string, to check for the relevant characters. However, this was prohibitively slow as expected.

A much better solution that I tried, involved first computing all the ‘lucky numbers’ which had the number of digits between the number of digits that a and b have (by counting possible combinations):

long n = 0;

for (int occurrences = 1; occurrences <= maxDigits; occurrences++) {

    n += (long) Math.pow(8, digits - occurrences) * choose(digits, occurrences);
}

return 2 * n;

and then using the brute force method to compute the number of extra lucky numbers that I had counted. So for example, if a = 3 and b = 21, I could count the number of 1 and 2 digit lucky numbers, then subtract the count of those in [1, 3) and (21, 99].

However, although this was a massive improvement, the brute force element still slowed it down way too much for most cases.

I feel like there must be something I am missing, as the rest of the interview questions were relatively simple. Does anyone have any idea of a better solution?


Although I have tagged this question in Java, help in any other languages or pseudocode would be equally appreciated.

Advertisement

Answer

I would say you are at the right track. The gut feeling is that dealing with the a and b separately is easier. Making a function count_lucky_numbers_below(n) allows

return count_lucky_numbers_below(b) - count_lucky_numbers_below(a);

The combinatorial approach is definitely a way to go (just keep in mind that the sum is actually equal to 9**n - 8**n, and there is no need to compute the binomial coefficients).

The final trick is to recurse down by a numbeer of digits.

Lets say n is an N-digit number, and the most significant digit is 5. Each set of N-digit numbers starting with a smaller digit contributes S = 9**(N-1) - 8**(N-1) to the total; you immediately have 5*S of lucky numbers. To deal with the remainder, you need to compute the lucky numbers for the N-1-digit tail.

Of course, care must be taken if the most significant digit is above 5. You need to special case it being 6 or 8, but it doesn’t seem to be too complicated.

User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement