Numbers With Repeated Digits

• Initialize a counter count to 0.
• Loop through each integer i from 1 to n.
• For each i, call a helper function hasRepeatedDigits(i).
• If the helper function returns true, increment count.
• Return count after the loop finishes.

Helper function hasRepeatedDigits(num):

• Create a boolean array seen of size 10, initialized to false.
• While num is greater than 0:
  • Extract the last digit: digit = num % 10.
  • If seen[digit] is already true, it means the digit is repeated, so return true.
  • Mark the digit as seen: seen[digit] = true.
  • Remove the last digit: num = num / 10.
• If the loop completes without finding repeated digits, return false.

The algorithm begins by initializing a counter, count, to zero. It then enters a loop that iterates through each number i from 1 up to the given integer n. Inside this loop, a helper function, hasRepeatedDigits(i), is invoked to determine if the current number i has any duplicate digits.

The hasRepeatedDigits function works by examining the digits of the number one by one. It uses a boolean array of size 10 as a frequency map to keep track of the digits it has already encountered. It extracts digits from the number using the modulo (%) and division (/) operators. If it encounters a digit that is already marked as seen in the frequency map, it immediately returns true, indicating a repeated digit. If it processes all digits without finding any repeats, it returns false.

Back in the main loop, if the helper function returns true, the count is incremented. After checking all numbers up to n, the final count is returned, which represents the total number of integers in the range [1, n] with at least one repeated digit.

1class Solution {2    public int numDupDigitsAtMostN(int n) {3        int count = 0;4        for (int i = 1; i <= n; i++) {5            if (hasRepeatedDigits(i)) {6                count++;7            }8        }9        return count;10    }11 12    private boolean hasRepeatedDigits(int num) {13        boolean[] seen = new boolean[10];14        while (num > 0) {15            int digit = num % 10;16            if (seen[digit]) {17                return true;18            }19            seen[digit] = true;20            num /= 10;21        }22        return false;23    }24}

• The problem is transformed to find the count of numbers with unique digits up to n, let's call it countUnique. The final answer is n - countUnique.
• Convert n to its string representation S of length L.
• Step 1: Count unique-digit numbers with fewer digits than n.
  • Iterate for length d from 1 to L-1.
  • For each d, the count of d-digit numbers with unique digits is 9 * P(9, d-1). Sum these values.
• Step 2: Count unique-digit numbers with the same number of digits as n.
  • Iterate through the digits of S from left to right (index i). Maintain a set of used digits from the prefix of n.
  • For the current digit S[i], iterate through all possible smaller digits d < S[i] that have not been used.
  • For each such valid d, add P(10 - (i+1), L - (i+1)) to the count. This represents forming a number with a smaller prefix.
  • After checking smaller digits, if S[i] itself has already been used, break the loop.
  • Otherwise, add S[i] to the used set and continue to the next position.
• Step 3: Account for n itself.
  • If the loop in Step 2 completes without breaking, it means n itself has unique digits, so add 1 to countUnique.
• Return n - countUnique.

This approach cleverly avoids iterating through all numbers. Instead, it counts the numbers with all unique digits up to n and subtracts this from n.

Let n be represented as a string S of length L. The counting of unique-digit numbers is done in two main parts:

1. Count unique-digit numbers with fewer digits than n: We calculate the number of unique-digit numbers for each length from 1 up to L-1.

   • For length 1, there are 9 (1-9).
   • For a length d > 1, the first digit has 9 choices (1-9), the second has 9 choices (0-9, excluding the first), the third has 8, and so on. The total for length d is 9 * P(9, d-1), where P(m, k) is the number of k-permutations of m. We sum these counts.

2. Count unique-digit numbers with length L and less than or equal to n: We iterate through the digits of n from left to right (most significant to least significant). We maintain a set of digits already used in the prefix of the number we are building.

   • At each position i (with digit d_i from n), we count the number of ways to form a valid L-digit number by choosing a digit smaller than d_i for this position. For each valid smaller digit j (not 0 for the first position and not already used), we can fill the remaining L-1-i positions in P(10 - (i+1), L-1-i) ways. We add this to our count.
   • After considering all smaller digits, we 'fix' the digit d_i at the current position. If d_i has already been used in the prefix, we must stop, as any number starting with this prefix will have repeated digits. Otherwise, we add d_i to our set of used digits and proceed to the next position.

Finally, if the process completes for all digits of n without stopping (which means n itself has unique digits), we add 1 to our count of unique-digit numbers.

1class Solution {2    public int numDupDigitsAtMostN(int n) {3        // Count numbers with unique digits, then subtract from n.4        return n - countUniqueDigits(n);5    }6 7    // Counts numbers with all unique digits from 1 to n.8    private int countUniqueDigits(int n) {9        String s = String.valueOf(n);10        int L = s.length();11        int res = 0;12 13        // 1. Count unique digit numbers with length < L14        for (int i = 1; i < L; i++) {15            res += 9 * permutation(9, i - 1);16        }17 18        // 2. Count unique digit numbers with length == L19        boolean[] used = new boolean[10];20        for (int i = 0; i < L; i++) {21            int digit = s.charAt(i) - '0';22            // Count numbers with the same prefix but a smaller digit at the current position23            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {24                if (!used[d]) {25                    res += permutation(10 - (i + 1), L - (i + 1));26                }27            }28            // If the current digit has been used, all subsequent numbers with this prefix will have duplicates.29            if (used[digit]) {30                return res; // Return the count so far31            }32            used[digit] = true;33        }34 35        // 3. If n itself has unique digits, add 136        return res + 1;37    }38 39    // Helper to calculate permutation P(m, n)40    private int permutation(int m, int n) {41        if (n < 0 || n > m) return 0;42        if (n == 0) return 1;43        int res = 1;44        for (int i = 0; i < n; i++) {45            res *= (m - i);46        }47        return res;48    }49}