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

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.

In the end the answer from @user58697 pushed me in the right direction towards finding a solution. With my (albeit extremely primitive) benchmark, it handles 1 to 2^63 - 1 in less than 2 nanoseconds, so it is definitely fast enough. However it is still more verbose than I would have liked, especially given that I was originally expected to write it in half an hour, so I feel like there is still an easier solution that gives comparable performance.

long countLuckyNumbersBetween(long a, long b) {

    return countLuckyNumbersBelow(b) - countLuckyNumbersBelow(a - 1);
}

long countLuckyNumbersBelow(long n) {

    return countNumbers(n, 6, 8) + countNumbers(n, 8, 6);
}

/**
 * Counts the natural numbers in [0, {to}] that have {including} as a digit, but not {excluding}.
 * {excluding} should be in (0, 9] or -1 to exclude no digit.
 */
long countNumbers(long to, int including, int excluding) {

    if (including == -1) return 0;

    if (to < 10) {

        if (to >= including) {

            return 1;
        } else {

            return 0;
        }
    }

    int nSignificand = significand(to);
    int nDigits = countDigits(to);

    long nTail = to % (long) Math.pow(10, nDigits - 1);

    // The count of numbers in [0, 10^(nDigits-1)) that include and exclude the relevant digits
    long bodyCount;
    if (excluding == -1) {

        bodyCount = (long) (Math.pow(10, nDigits - 1) - Math.pow(9, nDigits - 1));
    } else {

        bodyCount = (long) (Math.pow(9, nDigits - 1) - Math.pow(8, nDigits - 1));
    }

    long count = 0;

    for (int i = 0; i < nSignificand; i++) {

        if (i == including) {

            if (excluding == -1) {

                count += Math.pow(10, nDigits - 1);
            } else {

                count += Math.pow(9, nDigits - 1);
            }
        } else if (i != excluding) {

            count += bodyCount;
        }
    }

    if (nSignificand == including) {

        count += 1 + nTail - countNumbers(nTail, excluding, -1);
    } else if (nSignificand != excluding) {

        count += countNumbers(nTail, including, excluding);
    }

    return count;
}

int significand(long n) {

    while (n > 9) n /= 10;
    return (int) n;
}

int countDigits(long n) {

    if (n <= 1) {

        return 1;
    } else {

        return (int) (Math.log10(n) + 1);
    }
}

Here is another approach:

2⁶⁴ = 18446744073709551616

We can represent the number as a sum of components (one component per every digit position):

  18446744073709551616              associated range of numbers
  ————————————————————      ———————————————————————————————————————————
  0xxxxxxxxxxxxxxxxxxx  =>  [00000000000000000000;09999999999999999999]
  17xxxxxxxxxxxxxxxxxx  =>  [10000000000000000000;17999999999999999999]
  183xxxxxxxxxxxxxxxxx  =>  [18000000000000000000;18399999999999999999]
  1843xxxxxxxxxxxxxxxx  =>  [18400000000000000000;18439999999999999999]
  18445xxxxxxxxxxxxxxx  =>  [18440000000000000000;18445999999999999999]
  ...
  1844674407370955160x  =>  [18446744073709551600;18446744073709551609]
  18446744073709551616  =>  [18446744073709551610;18446744073709551616]

If we could compute the amount of lucky numbers for every component, then the sum of the amounts for every component will be the total amount for 2⁶⁴.

Note that every component consists of a prefix followed by xs.
Imagine that we know how many lucky numbers there are in an n-digit xx..x (i.e. numbers [0..0 - 9..9]), let's call it N(n).

Now let's look at a component 18445x..x. where 18445 is a prefix and an n-digit xx..x.
In this component we look at all numbers from 18440xx..x to 18445xx..x.
For every item 1844dxx..x we look at the prefix 1844d:

• if prefix contains no 6 or 8, then it's the same as x..x without prefix => N(n) special numbers
• if prefix contains 6 and no 8, then x..x cannot contain 8 => 9ⁿ special numbers
• if prefix contains 8 and no 6, then x..x cannot contain 6 => 9ⁿ special numbers
• if prefix contains 6 and 8 => 0 special numbers

Now let's compute N(n) — the amount of lucky numbers in an n-digit xx..x (i.e. in [0..0 - 9..9]).
We can do it iteratively:

1. n=1: there are only 2 possible numbers: 8 and 6 => N(1)=2.

2. n=2: there are 2 groups:

   • 8 present: 8x and x8 where x is any digit except 6
   • 6 present: 6x and x6 where x is any digit except 8

   => N(2)=4*9=34.

3. n=3: let's fix the 1st digit:

   • 0xx — 5xx, 7xx, 9xx => 8 * N(2)
   • 6xx: xx are any 2 digits except 8 => 9²
   • 8xx: xx are any 2 digits except 6 => 9² => N(3) = 8*N(2) + 2*9².

4. n=k+1 => N(k+1) = 7*N(k) + 2*9ᵏ

Here is an implementation (not 100% tested):

public final class Numbers {

  public long countLuckyNumbersBelow(BigInteger num) {
    if (num.compareTo(BigInteger.ZERO) < 0) {
      throw new IllegalArgumentException("num < 0: " + num);
    }
    var numberText = num.toString();
    var result = 0L;
    for (var digitPosition = 0; digitPosition < numberText.length(); digitPosition++) {
      result += countLuckyNumbersForComponent(numberText, digitPosition);
    }
    return result;
  }

  private long countLuckyNumbersForComponent(String numberText, int digitPosition) {
    var prefixEndIdx = numberText.length() - 1 - digitPosition;
    var prefixHas6s = containsChar(numberText, '6', prefixEndIdx);
    var prefixHas8s = containsChar(numberText, '8', prefixEndIdx);
    if (prefixHas6s && prefixHas8s) {
      return 0;
    }
    var result = 0L;
    for (var c = numberText.charAt(prefixEndIdx) - 1; c >= '0'; c--) {
      var compNo6s = (!prefixHas6s) && (c != '6');
      var compNo8s = (!prefixHas8s) && (c != '8');
      if (compNo6s && compNo8s) {
        result += countLuckyNumbers(digitPosition);
      } else if (compNo6s || compNo8s) {
        result += power9(digitPosition);
      }
    }
    return result;
  }

  private static boolean containsChar(String text, char c, int endIdx) {
    var idx = text.indexOf(c);
    return (idx > 0) && (idx < endIdx);
  }

  private long[] countLuckyNumbersCache = {0L, 0L};

  /**
   * Computes how many lucky numbers are in an n-digit `xx..x`
   */
  private long countLuckyNumbers(int numDigits) {
    if (countLuckyNumbersCache[0] == numDigits) {
      return countLuckyNumbersCache[1];
    }
    long N;
    if (numDigits <= 1) {
      N = (numDigits == 1) ? 2 : 0;
    } else {
      var prevN = countLuckyNumbers(numDigits - 1);
      N = (8 * prevN) + (2 * power9(numDigits-1));
    }
    countLuckyNumbersCache[0] = numDigits;
    countLuckyNumbersCache[1] = N;
    return N;
  }

  private long[] power9Cache = {0L, 1L};

  /**
   * Computes 9<sup>power</sup>
   */
  private long power9(int power) {
    if (power9Cache[0] == power) {
      return power9Cache[1];
    }
    long res = 1;
    var p = power;
    if (power > power9Cache[0]) {
      p -= power9Cache[0];
      res = power9Cache[1];
    }
    for (; p > 0; p--) {
      res *= 9;
    }
    power9Cache[0] = power;
    power9Cache[1] = res;
    return res;
  }
}

BTW it took me half a day, and I have no idea how is that possible to complete it in 30 minutes.
I guess your interviewers expected from you to demonstrate them your thought process.

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:

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();
  }