Leetcode: 357. Count Numbers with Unique Digits

The brute-force approach consists on iterating over all numbers between 0 and \(x\) and counting ones that have only unique digits. The following algorithm has time complexity of \(x \times 16\) which is \(16\times10^8 = 1,600,000,000\) in the worst-case scenario. The 16 factor comes from the fact that each number needs to be decomposed on digits twice.

None

This problem can be solved using Dynamic Programming by Digit. The numbers are generated digit while the used digits are kept on a set to avoid the same digit to be used twice. It also needs to keep an extra variable to flag when the digit zero can be used, since the leading zeros aren't count as digits in the number. There are \(x \times 2^{10} \times 2 \leq 8 \times 2^{10} \times 2 = 2^{14} = 16\,384\) different possible states, where \(x\) is the number of digits to be generated, \(2^10\) is the number of possible ways to select digits that are used in the number, and finally 2 for the zero flag. The following algorithm has time complexity of \(O(2^{14} \times 10)\).

Be \(f(x)\) the number of numbers with unique digits less or equal to \(x\). We have that \(f(0)=1\), \(f(1)=10\), \(f(2)=9\times9\) because there are 9 candidates for the first digit (\(1..9\)) and 9 candidates for the second digit (excluding the digit used in the first digit). For \(f(3)=z + f(2)\) where \(z\) is the number of number with unique digits and exactly 3 digits. There are 9 candidates for the first digit of \(z\), 9 for the second because 0 can be used but the number used on the first digit needs to be excluded, and finally 8 for the third. The same process can be applied when \(x\geq4\). The following algorithm has time complexity of \(O(x)\).

def count(x):
    if x == 0:
        return 1

    ans = 9
    for i in range(10 - x + 1, 10):
        ans = ans * i
    return ans + count(x - 1)


assert count(3) == 739
assert count(8) == 2345851


class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        return count(n)