2376. Count Special Integers
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].
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
int ncr[22][22];
int fac[22];
int nCr(int n, int r) {
if(r > n - r) return nCr(n, n-r);
if(r == 0) return 1;
if(ncr[n][r] != -1) return ncr[n][r];
return ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}
int fact(int n) {
if(n == 1) return 1;
if(fac[n] != -1) return fac[n];
return fac[n] = fact(n-1) * n;
}
int count(int n, int mask) {
if(!mask) return n;
int res = 0;
for(int i = 0; i <= n; i++) {
if(mask & (1<<i)) continue;
res++;
}
return res;
}
int helper(string s, bool low, int mask) {
if(s.length() == 0) return 0;
if(s.length() == 1) return count(stoi(s),mask);
int res = 0, len = s.length();
if(low) {
int use = 10 - __builtin_popcount(mask);
res += nCr(use, len) * fact(len);
} else {
for(int i = 0; i < s[0] - '0'; i++) {
if(mask & (1<<i)) continue;
if(i == 0) {
if(mask) res += helper(to_string((int)pow(10,len - 1) - 1), true, mask | 1);
else res += helper(to_string((int)pow(10,len - 1) - 1), false, mask);
}
else res += helper(to_string((int)pow(10,len - 1) - 1), true, mask | (1<<i));
}
if(!(mask & (1<<(s[0]-'0'))))
res += helper(s.substr(1), false, mask | (1<<(s[0]-'0')));
}
return res;
}
public:
int countSpecialNumbers(int n) {
memset(ncr,-1,sizeof ncr);
memset(fac, -1, sizeof fac);
return helper(to_string(n),false,0);
}
};
|
