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

Question

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.}

Answer 1

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.

Answer 2

Here is the result of my attempt.

First, let me explain a little bit what logic I used.

I used formula S = 9N — 8N (mentioned in the user58697's answer) to compute how many of N-digit numbers are lucky.
How to get this formula:

• for N-digit numbers there are 10N numbers in total: N digits, each can take one of 10 values: [0-9].
• if we only count numbers without 6, then each digit can only take one of 9 values [0-5,7-9] — it's 9N numbers in total
• now we also want only numbers with 8.
  We can easily compute how many numbers don't have both 6 and 8: digits in these numbers can only take one of 8 values [0-5,7,9] — it's 8N numbers in total.
  As a result, there are S = 9N — 8N numbers which have 8 and no 6.

For numbers with 6 and without 8 the formula is the same.
Also numbers without 6 do not intersect with numbers without 8 — so we can just sum them.

And finally, since we know how to count lucky numbers for intervals [0;10N], we need to split the interval [0; our arbitrary number] into suitable sub-intervals.
For instance, we can split number 9845637 this way:

Sub-interval	Prefix	Digit	N-digit interval
0000000 - 8999999		0 - 8	000000 - 999999
9000000 - 9799999	9	0 - 7	00000 - 99999
9800000 - 9839999	98	0 - 3	0000 - 9999
9840000 - 9844999	984	0 - 4	000 - 999
9845000 - 9845599	9845	0 - 5	00 - 99
9845600 - 9845629	98456	0 - 2	0 - 9
9845630 - 9845637

Now we can compute the number for every sub-interval (just keep attention to digits in prefix — they might contains 8 or 6) and then just sum those numbers to get the final result.

Here is the code:

  // Special value for 'requiredDigit': no required digit
  private static char NIL = Character.MAX_VALUE;

  public static long countLuckyNumbersUpTo(BigInteger number) {
    if (number.compareTo(BigInteger.ZERO) < 0) {
      throw new IllegalArgumentException("number < 0: " + number);
    }
    var numberAsDigits = number.toString();
    return countNumbersUpTo(numberAsDigits, '6', '8') + countNumbersUpTo(numberAsDigits, '8', '6');
  }

  // count all numbers in [0;'numberAsDigits'] which have 'requiredDigit' and no 'excludeDigit'
  private static long countNumbersUpTo(String numberAsDigits, char requiredDigit, char excludeDigit) {
    var highDigit = numberAsDigits.charAt(0);

    if (numberAsDigits.length() == 1) {
      return (requiredDigit != NIL)
          ? ((highDigit >= requiredDigit) ? 1 : 0)
          : numDigitsInInterval('0', highDigit, excludeDigit);
    }

    var tailDigits = numberAsDigits.substring(1);
    var result = 0L;

    // numbers where the highest digit is in [0;`highDigit`)
    var numGoodDigits = numDigitsInInterval('0', (char) (highDigit - 1), excludeDigit);
    var containsRequiredDigit = (requiredDigit != NIL) && (highDigit > requiredDigit);
    if (containsRequiredDigit) {
      result += totalNumbers(tailDigits.length(), NIL);
      numGoodDigits--;
    }
    if (numGoodDigits > 0) {
      result += numGoodDigits * totalNumbers(tailDigits.length(), requiredDigit);
    }

    // remaining numbers where the highest digit is `highDigit`
    if (highDigit != excludeDigit) {
      var newRequiredDigit = (highDigit == requiredDigit) ? NIL : requiredDigit;
      result += countNumbersUpTo(tailDigits, newRequiredDigit, excludeDigit);
    }

    return result;
  }

  private static int numDigitsInInterval(char firstDigit, char lastDigit, char excludeDigit) {
    var totalDigits = lastDigit - firstDigit + 1;
    return (excludeDigit <= lastDigit) ? (totalDigits - 1) : totalDigits;
  }

  // total numbers with given requiredDigit in [0;10^numDigits)
  private static long totalNumbers(int numDigits, char requiredDigit) {
    return (requiredDigit == NIL) ? pow(9, numDigits) : (pow(9, numDigits) - pow(8, numDigits));
  }

  private static long pow(int base, int exponent) {
    return BigInteger.valueOf(base).pow(exponent).longValueExact();
  }