2376. Count Special Integers

Posted on Edited on In

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:

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

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

Example 3:

1
2
3
4
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 * 10^9

Hints/Notes

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
32
33
34
35
class Solution {
public:
    string s;
    vector<vector<int>> dp;

    int countSpecialNumbers(int n) {
        s = to_string(n);
        dp.resize(s.size(), vector<int>(1024, -1));
        int res = dfs(0, 0, true, false);
        return res;
    }

    int dfs(int index, int mask, bool isLimit, bool is_num) {
        if (index == s.size()) {
            return is_num;
        }
        if (!isLimit && is_num && dp[index][mask] != -1) {
            return dp[index][mask];
        }
        int res = is_num ? 0 : dfs(index + 1, mask, false, false);
        int up = isLimit ? s[index] - '0' : 9;
        // if we start from 0 here when isNum is false, we are taking
        // 0 as a value answer
        for (int i = 1 - is_num; i <= up; i++) {
            if ((mask >> i & 1) == 0) {
                res += dfs(index + 1, mask | (1 << i), isLimit && i == up, true);
            }
        }
        // check status during read and write memo both
        if (!isLimit && is_num) {
            dp[index][mask] = res;
        }
        return res;
    }
};