Code Implementation

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        def count_unique(n):
            digits = list(map(int, str(n + 1)))
            n_digits = len(digits)
            res = 0

            # count numbers with length less than n_digits
            for i in range(1, n_digits):
                res += 9 * perm(9, i - 1)

            # count numbers with length == n_digits
            seen = set()
            for i, x in enumerate(digits):
                for y in range(0 if i else 1, x):
                    if y in seen:
                        continue
                    res += perm(9 - i, n_digits - i - 1)
                if x in seen:
                    break
                seen.add(x)
            return res

        def perm(m, n):
            res = 1
            for i in range(n):
                res *= m - i
            return res

        return N - count_unique(N)
      

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        vector digits;
        int n = N + 1;
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
        reverse(digits.begin(), digits.end());
        int n_digits = digits.size();
        int res = 0;

        // count numbers with length less than n_digits
        for (int i = 1; i < n_digits; ++i) {
            res += 9 * perm(9, i - 1);
        }

        // count numbers with length == n_digits
        unordered_set<int> seen;
        for (int i = 0; i < n_digits; ++i) {
            for (int y = (i == 0 ? 1 : 0); y < digits[i]; ++y) {
                if (seen.count(y)) continue;
                res += perm(9 - i, n_digits - i - 1);
            }
            if (seen.count(digits[i])) break;
            seen.insert(digits[i]);
        }
        return N - res;
    }

    int perm(int m, int n) {
        int res = 1;
        for (int i = 0; i < n; ++i) {
            res *= (m - i);
        }
        return res;
    }
};
      

class Solution {
    public int numDupDigitsAtMostN(int N) {
        int[] digits = toDigits(N + 1);
        int nDigits = digits.length;
        int res = 0;

        // count numbers with length less than nDigits
        for (int i = 1; i < nDigits; ++i) {
            res += 9 * perm(9, i - 1);
        }

        // count numbers with length == nDigits
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < nDigits; ++i) {
            for (int y = (i == 0 ? 1 : 0); y < digits[i]; ++y) {
                if (seen.contains(y)) continue;
                res += perm(9 - i, nDigits - i - 1);
            }
            if (seen.contains(digits[i])) break;
            seen.add(digits[i]);
        }
        return N - res;
    }

    private int[] toDigits(int n) {
        String s = Integer.toString(n);
        int[] res = new int[s.length()];
        for (int i = 0; i < s.length(); ++i)
            res[i] = s.charAt(i) - '0';
        return res;
    }

    private int perm(int m, int n) {
        int res = 1;
        for (int i = 0; i < n; ++i)
            res *= (m - i);
        return res;
    }
}
      

var numDupDigitsAtMostN = function(N) {
    function perm(m, n) {
        let res = 1;
        for(let i = 0; i < n; ++i) res *= (m - i);
        return res;
    }
    function countUnique(n) {
        let digits = Array.from(String(n + 1), Number);
        let nDigits = digits.length;
        let res = 0;
        // count numbers with length less than nDigits
        for(let i = 1; i < nDigits; ++i) {
            res += 9 * perm(9, i - 1);
        }
        // count numbers with length == nDigits
        let seen = new Set();
        for(let i = 0; i < nDigits; ++i) {
            for(let y = (i === 0 ? 1 : 0); y < digits[i]; ++y) {
                if(seen.has(y)) continue;
                res += perm(9 - i, nDigits - i - 1);
            }
            if(seen.has(digits[i])) break;
            seen.add(digits[i]);
        }
        return res;
    }
    return N - countUnique(N);
};
      

Problem Description

Given a positive integer N, find how many positive integers less than or equal to N have at least one repeated digit.
In other words, for a given N, count all numbers x such that 1 ≤ x ≤ N and x contains at least one digit that appears more than once in its decimal representation.
Constraints:

• 1 ≤ N ≤ 10^9

Thought Process

At first glance, it might seem reasonable to check each number from 1 to N and see if it contains any repeated digits. For each number, we could convert it to a string or array of digits and check for duplicates. However, this approach is not practical for large values of N (up to one billion), as it would take too long.
To optimize, we notice that it's easier to count the numbers without any repeated digits (i.e., with all unique digits), and then subtract this count from N to get the answer. This is a classic application of the "complement principle" in combinatorics.
The challenging part is efficiently counting the numbers with all unique digits up to N. We need to consider numbers with fewer digits than N, as well as numbers with the same number of digits as N but less than or equal to N.

Solution Approach

• Step 1: Complement Principle
  Instead of counting numbers with repeated digits directly, count the numbers with all unique digits (let's call this unique_count), then subtract from N:
  result = N - unique_count
• Step 2: Counting Numbers With All Unique Digits
  • Numbers with fewer digits than N:
    For numbers with k digits (1 ≤ k < number of digits in N), the count is:
    9 * P(9, k-1)
    Where P(m, n) is the number of ways to arrange n digits from m options (permutations), and the first digit can't be zero.
  • Numbers with the same number of digits as N:
    We need to count numbers with unique digits that are less than or equal to N. This is done by traversing the digits of N from left to right, at each step counting the choices for the next digit that haven't been used yet and that keep the number below N.
• Step 3: Implementation Details
  • Use a helper function to calculate permutations P(m, n).
  • Use a set to keep track of already-used digits as we build numbers digit by digit.
  • If a digit repeats, break out early from the loop.
• Step 4: Return the Result
  Return N - unique_count, which is the number of numbers with at least one repeated digit.

Example Walkthrough

Let's walk through the process with N = 100.

Step 1: Count numbers with all unique digits up to 100.

• 1-digit numbers: All numbers from 1 to 9 (since 0 is not allowed as the first digit). There are 9 such numbers.
• 2-digit numbers:
  • The first digit can be 1-9 (9 choices).
  • The second digit can be any digit except the first (9 choices, including 0).
  • Total: 9 * 9 = 81
• Numbers with 3 digits or more: 100 is a 3-digit number, but since 100 is exactly 100, we need to check if 100 itself has unique digits. 1, 0, 0: the digit 0 is repeated, so 100 is not counted as unique.
• Total unique-digit numbers: 9 (1-digit) + 81 (2-digit) = 90
• Result: 100 - 90 = 10 numbers with repeated digits between 1 and 100.

The repeated-digit numbers in this range are: 11, 22, 33, 44, 55, 66, 77, 88, 99, 100.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N * D), where D is the number of digits in N (for checking duplicates in each number). This is infeasible for large N (up to 10⁹).
• Space Complexity: O(1) or O(D) per number, negligible compared to time.

• Time Complexity: O(D²), where D is the number of digits in N. This comes from iterating over each digit and checking available choices/permutations.
• Space Complexity: O(D) for storing the used digits and digit arrays.

This is efficient enough for N up to 10⁹.

Summary

The key insight is to use the complement principle: instead of counting numbers with repeated digits directly, count the numbers with all unique digits and subtract from N. By using combinatorics and careful digit-by-digit traversal, we efficiently count unique-digit numbers up to N. This avoids brute-force enumeration, making the algorithm fast even for large N. The solution elegantly combines combinatorial counting with digit dynamic programming principles, making it both efficient and instructive.