Skip to content

357. Count Numbers with Unique Digits

Difficulty Topics

Description

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.

 

Example 1:

Input: n = 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

Example 2:

Input: n = 0
Output: 1

 

Constraints:

  • 0 <= n <= 8

Solution

count-numbers-with-unique-digits.py
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0: return 1

        n = (10 ** n) - 1
        digits = []

        while n > 0:
            digits.append(n % 10)
            n //= 10

        digits.reverse()
        N = len(digits)

        @cache
        def dp(pos, tight, mask):
            if pos == N:
                return 1

            limit = digits[pos] if tight else 9
            res = 0

            for i in range(0, limit + 1):
                if mask & (1 << i) > 0: continue

                nextTight = tight and i == digits[pos]
                nextMask = mask if i == 0 and mask == 0 else mask ^ (1 << i)

                res += dp(pos + 1, nextTight, nextMask)

            return res

        return dp(0, True, 0)