Numbers With Repeated Digits LeetCode solution in Java

1
class Solution {
2
  public int numDupDigitsAtMostN(int n) {
3
    // 983582
4
    // 108318
5
    int ttl = n++;
6
    int ans = 0;
7
    List<Integer> list = new ArrayList<>();
8
    while (n > 0) {
9
      list.add(n % 10);
10
      n /= 10;
11
    }
12
    for (int i = 1; i < list.size(); i++) {
13
      ans += 9 * find(i - 1, 9);
14
    }
15
    boolean[] seen = new boolean[10];
16
    for (int i = list.size(), d = 9; i > 0; --i, d--) {
17
      int count = i == list.size() ? list.get(i - 1) - 1 : list.get(i - 1);
18
      for (int j = 0; j < list.get(i - 1); j++) {
19
        if (seen[j]) {
20
          count--;
21
        }
22
      }
23
      ans += count * find(i - 1, d);
24
      if (seen[list.get(i - 1)]) {
25
        break;
26
      }
27
      seen[list.get(i - 1)] = true;
28
    }
29
    return ttl - ans;
30
  }
31

32
  private int find(int n, int d) {
33
    // dCn*n!
34
    // d!/(d-n)/(d-n).../1
35
    int ans = 1;
36
    for (int i = 1; i <= d; i++) {
37
      ans *= i;
38
    }
39
    for (int i = n + 1; i <= d; i++) {
40
      ans /= (i - n);
41
    }
42
    return ans;
43
  }
44
}