# Numbers With Repeated Digits

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

```Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
```
Example 2:

```Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
```
Example 3:

```Input: 1000
Output: 262
```

Note:

1. 1 <= N <= 10^9

Solution:

```class Solution {
public int numDupDigitsAtMostN(int N) {
int noRepeat = 0;

// Transform N + 1 to arrayList
List<Integer> L = new ArrayList<Integer>();
for (int x = N + 1; x > 0; x /= 10)

// Count the number with digits < N
for (int i = 0; i < L.size() - 1; i ++) {
noRepeat += 9 * p(9, i);
}

// Count the number with same prefix
// 1XXX ~ 7XXX
// 80XX ~ 86XX
// 870X ~ 875X
// 8760 ~ 8765
Set<Integer> seen = new HashSet();
for (int i = 0; i < L.size(); i ++) {
int curr = L.get(i);
for (int j = i == 0 ? 1 : 0; j < curr; j ++) {
if (!seen.contains(j)) {
noRepeat += p(9 - i, L.size() - 1 - i);
}
}
}

return N - noRepeat;
}

private int p(int m, int n) {
if (n == 0) return 1;
return factorial(m) / factorial(m - n);
}

private int factorial(int n) {
int val = 1;
for (int i = 1; i <= n; i ++) {
val = val * i;
}
return val;
}
}```