357. Count Numbers with Unique Digits
Đề Bài
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
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
Python
0357-count-numbers-with-unique-digits.py
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
nums = list(map(int, str(10 ** n - 1)))
sz = len(nums)
@cache
def dp(i, tight, mask):
if i == sz:
return 1
limit = nums[i] if tight else 9
limit += 1
ans = 0
for d in range(limit):
if mask & (1 << d):
continue
newTight = tight and d == nums[i]
newMask = mask if mask == 0 and d == 0 else mask | (1 << d)
ans += dp(i + 1, newTight, newMask)
return ans
return dp(0, True, 0)