Numbers With Repeated Digits LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long int dp[11][2][2][(1 << 10)];
4
  int f(int idx, bool flag, bool repeat, int mask, string &s) {
5
    if (idx == s.size()) {
6
      return repeat;
7
    }
8

9
    if (dp[idx][flag][repeat][mask] != -1) return dp[idx][flag][repeat][mask];
10

11
    int limit = s[idx] - '0';
12
    if (flag) limit = 9;
13

14
    int ans = 0;
15

16
    for (int digit = 0; digit <= limit; digit++) {
17
      if (digit < (s[idx] - '0')) {
18
        if (digit == 0 and mask == 0) {
19
          ans += f(idx + 1, true, false, mask, s);
20
        }
21

22
        else if (mask & (1 << digit)) {
23
          ans += f(idx + 1, true, true, mask, s);
24
        } else {
25
          ans += f(idx + 1, true, repeat, mask | (1 << digit), s);
26
        }
27

28
      } else {
29
        if (digit == 0 and mask == 0) {
30
          ans += f(idx + 1, flag, false, mask, s);
31
        }
32

33
        else if (mask & (1 << digit)) {
34
          ans += f(idx + 1, flag, true, mask, s);
35
        } else {
36
          ans += f(idx + 1, flag, repeat, mask | (1 << digit), s);
37
        }
38
      }
39
    }
40

41
    return dp[idx][flag][repeat][mask] = ans;
42
  }
43
  int numDupDigitsAtMostN(int n) {
44
    string r = to_string(n);
45
    memset(dp, -1, sizeof dp);
46

47
    return f(0, false, false, 0, r);
48
  }