# Count Numbers with Unique Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-numbers-with-unique-digits)
Canonical: https://scaleengineer.com/dsa/problems/count-numbers-with-unique-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
Given an integer `n`, return the count of all numbers with unique digits, `x`, where `0 <= x < 10n`.

**Example 1:**

**Input:** n = 2
**Output:** 91
**Explanation:** The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

**Example 2:**

**Input:** n = 0
**Output:** 1

**Constraints:**

* `0 <= n <= 8`

# Approaches
## Brute Force Iteration
This approach involves iterating through every number from 0 up to `10^n - 1` and checking if each number has unique digits. A helper function is used to determine if a number's digits are all distinct.
**Time:** O(n * 10^n). The loop runs `10^n` times. The check for unique digits takes `O(log10(i))` time, which is at most `O(n)`. This approach is very slow and will time out for larger values of `n`. · **Space:** O(1). The space used by the `seen` array is constant (size 10).
**Pros:** Simple to understand and implement.; Directly follows the problem definition.
**Cons:** Extremely inefficient.; Will not pass for `n` greater than 6 or 7 due to Time Limit Exceeded errors.
### Explanation
We loop through all integers `x` in the range `[0, 10^n)`. For each integer `x`, we check if its digits are unique. To check for uniqueness, we can convert the number to a sequence of its digits. A boolean array or a hash set can be used to keep track of the digits seen so far. If a digit is encountered more than once, the number does not have unique digits. We maintain a counter, which is incremented for every number that satisfies the unique digit property. The final value of the counter is the result.

```java
class Solution {
    private boolean hasUniqueDigits(int n) {
        boolean[] seen = new boolean[10];
        String s = String.valueOf(n);
        for (char c : s.toCharArray()) {
            if (seen[c - '0']) {
                return false;
            }
            seen[c - '0'] = true;
        }
        return true;
    }

    public int countNumbersWithUniqueDigits(int n) {
        if (n > 10) {
            n = 10;
        }
        int limit = (int) Math.pow(10, n);
        int count = 0;
        for (int i = 0; i < limit; i++) {
            if (hasUniqueDigits(i)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Calculate the upper limit of the range, `limit = 10^n`.
- Iterate with a variable `i` from 0 to `limit - 1`.
- For each `i`, call a helper function `hasUniqueDigits(i)`.
  - Inside `hasUniqueDigits(num)`:
    - Create a boolean array `seen` of size 10, initialized to `false`.
    - Repeatedly take the last digit of `num` (`num % 10`).
    - If the digit has been seen before (i.e., `seen[digit]` is `true`), return `false`.
    - Mark the digit as seen by setting `seen[digit]` to `true`.
    - Update `num` by dividing it by 10.
    - If the loop completes, all digits are unique, so return `true`.
- If `hasUniqueDigits(i)` returns `true`, increment `count`.
- After the loop, return `count`.

## Backtracking
This approach builds numbers with unique digits recursively. We can think of it as exploring a decision tree where each level corresponds to a digit's position, and each branch is a choice of a digit (0-9) that has not been used yet.
**Time:** The number of states is related to the number of valid prefixes. For `n=8`, this is `1 + 9 + 9*9 + 9*9*8 + ...`. This is much smaller than `10^n`. The complexity is roughly proportional to the number of unique-digit numbers, which is the answer itself. · **Space:** O(n) for the recursion depth.
**Pros:** More efficient than brute force.; Explores only the valid search space of numbers with unique digits.
**Cons:** More complex to implement correctly than brute force.; Can be less intuitive than the direct combinatorial approach.; The recursive implementation might have overhead.
### Explanation
The core idea is to count the valid numbers by constructing them. A number is a sequence of digits. We can use a backtracking function to explore all possible valid sequences. The state of our backtracking function can be `(current_length, used_digits_mask)`. `current_length` is the number of digits in the number being built, and `used_digits_mask` is a bitmask representing the set of digits already used. The total count is the sum of counts for numbers of length 1, 2, ..., up to `n`. We must handle the leading zero case: a number cannot start with 0 unless it is the number 0 itself.

```java
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n > 10) {
            return countNumbersWithUniqueDigits(10);
        }
        // Count numbers with length < n
        // Start with 1 for the number 0
        int count = 1; 
        long max = (long) Math.pow(10, n);
        boolean[] used = new boolean[10];
        
        // Count numbers with length 1 to n starting with 1-9
        for (int i = 1; i <= 9; i++) {
            used[i] = true;
            count += backtrack(i, max, used);
            used[i] = false;
        }
        return count;
    }
    
    private int backtrack(long currentNum, long max, boolean[] used) {
        int count = 0;
        if (currentNum < max) {
            count = 1;
        } else {
            return 0;
        }
        
        for (int i = 0; i <= 9; i++) {
            if (!used[i]) {
                used[i] = true;
                long nextNum = currentNum * 10 + i;
                if (nextNum < max) {
                    count += backtrack(nextNum, max, used);
                }
                used[i] = false;
            }
        }
        return count;
    }
}
```
### Algorithm
- The problem is to count numbers `x` in `0 <= x < 10^n` with unique digits.
- This is equivalent to counting all numbers with unique digits that have a length from 1 to `n`.
- We can define a recursive function, say `backtrack(current_number, used_digits_mask)`.
- The function explores adding a new digit to `current_number`.
- Start with `count = 1` (for the number 0).
- The initial calls to backtracking would be for single-digit numbers (1 to 9).
- `backtrack(current_num, max_val, used_mask)`:
  - `count = 1` (for `current_num` itself).
  - For each digit `d` from 0 to 9:
    - If `d` is not in `used_mask`:
      - Form `next_num = current_num * 10 + d`.
      - If `next_num < max_val`:
        - Add the result of `backtrack(next_num, max_val, new_mask)` to `count`.
- The initial calls would be `backtrack(i, 10^n, mask_for_i)` for `i` from 1 to 9.

## Dynamic Programming / Combinatorics
This is the most efficient approach, leveraging mathematical principles of permutations and combinations. We can calculate the count of unique-digit numbers for each possible length (from 1 to `n`) and sum them up.
**Time:** O(n). The loop runs at most `n-1` times. Since `n` is small (`<= 8`), this is effectively constant time, O(1). · **Space:** O(1). We only use a few variables to store the intermediate and final counts.
**Pros:** Extremely efficient in both time and space.; Provides a direct calculation without unnecessary exploration.; Simple and concise implementation.
**Cons:** Requires understanding the underlying combinatorial logic, which might be less obvious than a brute-force approach.
### Explanation
Let `f(k)` be the count of numbers with unique digits of length `k`. The total count for a given `n` is the sum of `f(k)` for `k` from 1 to `n`.
- For `k=1`: The numbers are 0, 1, ..., 9. All 10 have unique digits. So, the count is 10.
- For `k=2`: A 2-digit number `ab` has `a` in {1..9} (9 choices) and `b` in {0..9} where `b != a` (9 choices). So, the count is `9 * 9 = 81`.
- For `k=3`: A 3-digit number `abc` has `a` in {1..9} (9 choices), `b` in {0..9} \ {a} (9 choices), and `c` in {0..9} \ {a, b} (8 choices). So, the count is `9 * 9 * 8 = 648`.
- In general, for `k > 1`, the count is `9 * P(9, k-1) = 9 * 9 * 8 * ... * (10 - k + 1)`.
We can observe a recurrence relation. The count for length `k` can be derived from the count for length `k-1`. We can compute these values iteratively and add them to a running total.

```java
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        
        // The problem asks for numbers in the range [0, 10^n).
        // This is equivalent to counting numbers with unique digits of length 1, 2, ..., n.
        
        // For n=1, the numbers are 0, 1, ..., 9. All 10 have unique digits.
        int totalCount = 10; 
        
        // For numbers with length k > 1.
        // The first digit has 9 choices (1-9).
        // The second digit has 9 choices (0-9, excluding the first).
        // The third digit has 8 choices.
        // And so on.
        
        int uniqueDigitsForK = 9; // Count for length k, starting with k=2. First digit has 9 choices.
        int availableChoices = 9; // Choices for subsequent digits.
        
        // Loop for lengths from 2 to n.
        // Math.min(n, 10) because for n > 10, no new unique digit numbers can be formed.
        for (int k = 2; k <= Math.min(n, 10); k++) {
            uniqueDigitsForK = uniqueDigitsForK * availableChoices;
            totalCount += uniqueDigitsForK;
            availableChoices--;
        }
        
        return totalCount;
    }
}
```
### Algorithm
- Handle the base case: if `n = 0`, return 1.
- Initialize `totalCount = 10` (this covers all 1-digit numbers with unique digits).
- Initialize `uniqueDigitsForK = 9` (this represents the number of ways to choose the first digit for numbers with length > 1, i.e., from 1-9).
- Initialize `availableChoices = 9` (this represents the number of choices for the second digit).
- Loop for length `k` from 2 up to `n` (or 10, whichever is smaller, as numbers with more than 10 digits cannot have unique digits).
  - In each iteration, calculate the count of unique-digit numbers of length `k`: `uniqueDigitsForK = uniqueDigitsForK * availableChoices`.
  - Add this count to `totalCount`.
  - Decrement `availableChoices` for the next iteration (as one more digit is now used).
- Return `totalCount`.

# Solutions
### Java

```java
class Solution {
public
  int countNumbersWithUniqueDigits(int n) {
    if (n == 0) {
      return 1;
    }
    if (n == 1) {
      return 10;
    }
    int ans = 10;
    for (int i = 0, cur = 9; i < n - 1; ++i) {
      cur *= (9 - i);
      ans += cur;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int: if n == 0: return 1 if n == 1: return 10 ans, cur = 10, 9 for i in range(n - 1): cur *= 9 - i ans += cur return ans

```

### CPP

```cpp
class Solution {
public:
  int countNumbersWithUniqueDigits(int n) {
    if (n == 0)
      return 1;
    if (n == 1)
      return 10;
    int ans = 10;
    for (int i = 0, cur = 9; i < n - 1; ++i) {
      cur *= (9 - i);
      ans += cur;
    }
    return ans;
  }
};

```