357. Count Numbers with Unique Digits

Posted on Edited on In

357. Count Numbers with Unique Digits

Description

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

Example 1:

1
2
3
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:

1
2
Input: n = 0
Output: 1

Constraints:

  • 0 <= n <= 8

Hints/Notes

  • 2024/11/20
  • digit dp with is_num
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int n;
    vector<vector<int>> dp;

    int countNumbersWithUniqueDigits(int n) {
        this->n = n;
        dp.resize(n, vector<int>(1024, -1));
        int res = dfs(0, 0, false);
        return res;
    }

    int dfs(int index, int mask, bool is_num) {
        if (index == n) {
            return 1;
        }
        if (is_num && dp[index][mask] != -1) {
            return dp[index][mask];
        }
        int res = is_num ? 0 : dfs(index + 1, mask, false);
        for (int i = 1 - is_num; i <= 9; i++) {
            if ((mask >> i & 1) == 0) {
                res += dfs(index + 1, mask | (1 << i), true);
            }
        }
        if (is_num) {
            dp[index][mask] = res;
        }
        return res;
    }
};