blob: ff73d9456d9c7fe00cda14b90ef22a2812a39047 (
plain)
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
53
54
55
56
57
58
59
|
// 2376. Count Special Integers
#include "leetcode.h"
/*
* 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]'
*/
int countSpecialNumbers(int n) {
if (n <= 10)
return n;
int ans = 0, k = 9, choose = 9, list[10], curr = 0;
list[curr] = n % 10;
n /= 10;
while (n) {
curr++;
ans += k;
k *= choose;
choose--;
list[curr] = n % 10;
n /= 10;
}
k /= 9;
bool used[10] = {0};
choose = 9;
if (curr) {
used[list[curr]] = 1;
ans += k * (list[curr] - 1);
k /= choose;
curr--;
}
while (curr) {
int first_choose = 0;
for (int i = 0; i < list[curr]; i++)
if (!used[i])
first_choose++;
curr--;
ans += first_choose * k;
choose--;
k /= choose;
if (used[list[curr + 1]])
return ans;
else
used[list[curr + 1]] = 1;
;
}
for (int i = 0; i <= list[curr]; i++)
if (!used[i])
ans++;
return ans;
}
int main() {
printf("%d\n", countSpecialNumbers(20)); // expect: 19
printf("%d\n", countSpecialNumbers(5)); // expect: 5
printf("%d\n", countSpecialNumbers(135)); // expect: 110
}
|