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)
            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;
    }
}