Numbers With Repeated Digits
IntuitionInstead of counting numbers with repeated digits directly, we use a complement approach:
Count numbers that only have unique digits (easier to compute)
# Intuition
Instead of counting numbers with repeated digits directly, we use a complement approach:
Count numbers that only have unique digits (easier to compute).
Subtract from n to get the count of numbers with at least one repeated digit.
Example
For n = 100, we count:

Unique digit numbers (1-100): {1, 2, 3, ..., 9, 10, 12, ..., 98}
Numbers with repeated digits: {11, 22, ..., 99, 100}
Answer: n - unique_count = 100 - 90 = 10
# Approach
Convert n to a digit array:
Example: 1000 → [1,0,0,0]
Count numbers with all unique digits:
For numbers with fewer digits (1 to d-1 digits):
Use permutations to count numbers with unique digits.
For numbers with the same length as n:
Use backtracking with a set to ensure uniqueness.
Compute the result using the complement principle:
Numbers with repeated digits
=
𝑛
−
Numbers with unique digits
Numbers with repeated digits=n−Numbers with unique digits

# Complexity
- Time complexity:O(logn) (as d ≤ 10 for n ≤ 10^9)
- Space complexity:O(1), since only a few variables are used
# Code
```java []
import java.util.*;

class Solution {
    public int numDupDigitsAtMostN(int n) {
        List<Integer> digits = new ArrayList<>();
        int temp = n + 1;  // To include 'n' in the calculation
        while (temp > 0) {
            digits.add(temp % 10);
            temp /= 10;
        }
        Collections.reverse(digits);
        
        int numDigits = digits.size();
        int uniqueCount = 0;

        // Count numbers with fewer digits
        for (int i = 1; i < numDigits; i++) {
            uniqueCount += countUniqueNumbersWithLength(i);
        }

        // Count numbers with the same length as 'n' but smaller
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < numDigits; i++) {
            int digit = digits.get(i);
            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {
                if (!seen.contains(d)) {
                    uniqueCount += countPermutations(9 - i, numDigits - i - 1);
                }
            }
            if (seen.contains(digit)) break;
            seen.add(digit);
        }

        return n - uniqueCount;
    }

    // Count numbers with unique digits for lengths < numDigits
    private int countUniqueNumbersWithLength(int length) {
        if (length == 1) return 9; // 1-9
        int count = 9, available = 9;
        for (int i = 1; i < length; i++) {
            count *= available;
            available--;
        }
        return count;
    }

    // Count valid numbers with unique digits using permutation formula
    private int countPermutations(int available, int length) {
        int count = 1;
        for (int i = 0; i < length; i++) {
            count *= available;
            available--;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDupDigitsAtMostN(20));   // Output: 1
        System.out.println(sol.numDupDigitsAtMostN(100));  // Output: 10
        System.out.println(sol.numDupDigitsAtMostN(1000)); // Output: 262
        
    }
}

```
['Java']