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 <= 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)
L.add(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);
}
}
if (!seen.add(curr)) break;
}
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;
}
}