# Numbers With Repeated Digits
**Difficulty:** HARD
[External](https://leetcode.com/problems/numbers-with-repeated-digits)
Canonical: https://scaleengineer.com/dsa/problems/numbers-with-repeated-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
Given an integer `n`, return _the number of positive integers in the range_ `[1, n]` _that have **at least one** repeated digit_.

**Example 1:**

**Input:** n = 20
**Output:** 1
**Explanation:** The only positive number (<= 20) with at least 1 repeated digit is 11.

**Example 2:**

**Input:** n = 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:** n = 1000
**Output:** 262

**Constraints:**

* `1 <= n <= 109`

# Approaches
## Brute Force Iteration
This approach involves a straightforward iteration through every integer from 1 to `n`. For each integer, it performs a check to see if it contains any repeated digits. A counter is maintained and incremented for each number that is found to have at least one repeated digit.
**Time:** O(n * log₁₀(n)). The main loop runs `n` times. For each number `i`, the `hasRepeatedDigits` function takes a number of steps proportional to the number of digits in `i`, which is `O(log₁₀(i))`. Given `n` can be up to 10⁹, this approach is too slow. · **Space:** O(1). The space required for the `seen` array is constant as it always has a size of 10, regardless of the input `n`.
**Pros:** Simple to understand and implement.; Correct for small values of `n`.
**Cons:** Highly inefficient for large values of `n`.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
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.

```java
class Solution {
    public int numDupDigitsAtMostN(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (hasRepeatedDigits(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean hasRepeatedDigits(int num) {
        boolean[] seen = new boolean[10];
        while (num > 0) {
            int digit = num % 10;
            if (seen[digit]) {
                return true;
            }
            seen[digit] = true;
            num /= 10;
        }
        return false;
    }
}
```
### Algorithm
- 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`.

## Combinatorics and Digit DP
A much more efficient method is to solve the complementary problem: counting the number of positive integers up to `n` that have *all unique digits*. If we find this count, let's call it `countUnique`, the final answer is simply `n - countUnique`. This technique is a form of Digit Dynamic Programming, where we build the count digit by digit based on the digits of `n`.
**Time:** O((log₁₀(n))²). The number of digits in `n` is `L = O(log₁₀(n))`. The main loops run `L` times. Inside the loops, calculating permutations also takes `O(L)` time, leading to a near-quadratic complexity with respect to the number of digits. · **Space:** O(log₁₀(n)). Space is required to store the digits of `n` as a string, which has a length of `O(log₁₀(n))`. The `used` array is of constant size.
**Pros:** Extremely efficient and fast, even for large `n`.; Scales logarithmically with the input `n`.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires knowledge of combinatorics (permutations).
### Explanation
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.

```java
class Solution {
    public int numDupDigitsAtMostN(int n) {
        // Count numbers with unique digits, then subtract from n.
        return n - countUniqueDigits(n);
    }

    // Counts numbers with all unique digits from 1 to n.
    private int countUniqueDigits(int n) {
        String s = String.valueOf(n);
        int L = s.length();
        int res = 0;

        // 1. Count unique digit numbers with length < L
        for (int i = 1; i < L; i++) {
            res += 9 * permutation(9, i - 1);
        }

        // 2. Count unique digit numbers with length == L
        boolean[] used = new boolean[10];
        for (int i = 0; i < L; i++) {
            int digit = s.charAt(i) - '0';
            // Count numbers with the same prefix but a smaller digit at the current position
            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {
                if (!used[d]) {
                    res += permutation(10 - (i + 1), L - (i + 1));
                }
            }
            // If the current digit has been used, all subsequent numbers with this prefix will have duplicates.
            if (used[digit]) {
                return res; // Return the count so far
            }
            used[digit] = true;
        }

        // 3. If n itself has unique digits, add 1
        return res + 1;
    }

    // Helper to calculate permutation P(m, n)
    private int permutation(int m, int n) {
        if (n < 0 || n > m) return 0;
        if (n == 0) return 1;
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= (m - i);
        }
        return res;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution {
private
  int[] nums = new int[11];
private
  Integer[][] dp = new Integer[11][1 << 11];
public
  int numDupDigitsAtMostN(int n) { return n - f(n); }
private
  int f(int n) {
    int i = -1;
    for (; n > 0; n /= 10) {
      nums[++i] = n % 10;
    }
    return dfs(i, 0, true, true);
  }
private
  int dfs(int pos, int mask, boolean lead, boolean limit) {
    if (pos < 0) {
      return lead ? 0 : 1;
    }
    if (!lead && !limit && dp[pos][mask] != null) {
      return dp[pos][mask];
    }
    int ans = 0;
    int up = limit ? nums[pos] : 9;
    for (int i = 0; i <= up; ++i) {
      if ((mask >> i & 1) == 1) {
        continue;
      }
      if (i == 0 && lead) {
        ans += dfs(pos - 1, mask, lead, limit && i == up);
      } else {
        ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
      }
    }
    if (!lead && !limit) {
      dp[pos][mask] = ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numDupDigitsAtMostN(int n) { return n - f(n); }

private:
  int nums[11];
  int dp[11][1 << 11];
  int f(int n) {
    memset(dp, -1, sizeof(dp));
    int i = -1;
    for (; n; n /= 10) {
      nums[++i] = n % 10;
    }
    return dfs(i, 0, true, true);
  }
  int dfs(int pos, int mask, bool lead, bool limit) {
    if (pos < 0) {
      return lead ? 0 : 1;
    }
    if (!lead && !limit && dp[pos][mask] != -1) {
      return dp[pos][mask];
    }
    int up = limit ? nums[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up; ++i) {
      if (mask >> i & 1) {
        continue;
      }
      if (i == 0 && lead) {
        ans += dfs(pos - 1, mask, lead, limit && i == up);
      } else {
        ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
      }
    }
    if (!lead && !limit) {
      dp[pos][mask] = ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int: return n - self . f(n) def f(self, n: int) -> int: @ cache def dfs(pos: int, mask: int, lead: bool, limit: bool) -> int: if pos < 0: return int(lead) ^ 1 up = nums[pos] if limit else 9 ans = 0 for i in range(up + 1): if mask >> i & 1: continue if i == 0 and lead: ans += dfs(pos - 1, mask, lead, limit and i == up) else: ans += dfs(pos - 1, mask | 1 << i, False, limit and i == up) return ans nums = [] while n: nums . append(n % 10) n //= 10 return dfs(len(nums) - 1, 0, True, True)

```