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
Python3
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)