2376. Count Special Integers

Description

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval [1, n].

 

Example 1:

Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Example 2:

Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.

Example 3:

Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

 

Constraints:

• 1 <= n <= 2 * 109

Solution

count-special-integers.py

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        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 if mask != 0 else 0

            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)