# Count Special Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-special-integers)
Canonical: https://scaleengineer.com/dsa/problems/count-special-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## Problem
We call a positive integer **special** if all of its digits are **distinct**.

Given a **positive** integer `n`, return _the number of special integers that belong to the interval_ `[1, n]`.

**Example 1:**

**Input:** n = 20
**Output:** 19
**Explanation:** All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

**Example 2:**

**Input:** n = 5
**Output:** 5
**Explanation:** All the integers from 1 to 5 are special.

**Example 3:**

**Input:** n = 135
**Output:** 110
**Explanation:** There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

**Constraints:**

* `1 <= n <= 2 * 109`

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the process directly. We can iterate through every integer from 1 up to `n` and, for each integer, check if it meets the criteria of being "special" (i.e., all its digits are distinct). We maintain a count of such numbers found.
**Time:** O(n * log10(n)). We iterate `n` times. For each number `i`, the `isSpecial` check takes O(log10(i)) time, as the number of digits is logarithmic with respect to the number's value. · **Space:** O(log10(n)) or O(1). The `isSpecial` function uses a boolean array of constant size 10. The space used for the number's digits is proportional to log10(n), which is small.
**Pros:** Very easy to understand and implement.; It's a good starting point for verifying the logic with small test cases.
**Cons:** The time complexity is directly proportional to `n`, which is too slow for the given constraints (`n` up to 2 * 10^9).; This approach will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
This method involves a simple loop from 1 to `n`. Inside the loop, a helper function, let's call it `isSpecial(num)`, determines if a number has unique digits. 

The `isSpecial` function can work by repeatedly taking the number modulo 10 to get the last digit and then dividing by 10 to process the next digit. 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 is not special.

Here is a code implementation of this approach:
```java
class Solution {
    // Helper function to check if a number has distinct digits
    private boolean isSpecial(int num) {
        boolean[] seen = new boolean[10];
        while (num > 0) {
            int digit = num % 10;
            if (seen[digit]) {
                return false;
            }
            seen[digit] = true;
            num /= 10;
        }
        return true;
    }

    public int countSpecialNumbers(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isSpecial(i)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `special_count` to 0.
2. Iterate through each integer `i` from 1 to `n`.
3. For each integer `i`, check if it is a "special integer".
   - To check if `i` is special, we can convert it to a sequence of its digits.
   - Use a frequency map or a set to keep track of the digits encountered.
   - Iterate through the digits. If a digit is already in our set, the number is not special. Otherwise, add the digit to the set.
   - If we process all digits without finding a duplicate, the number is special.
4. If `i` is a special integer, increment `special_count`.
5. After the loop finishes, return `special_count`.

## Digit DP with Combinatorics
A much more efficient method is to use digit dynamic programming, which builds the count based on the digits of `n`. Instead of checking every number, we can count the number of valid special integers mathematically. We can count the special integers with fewer digits than `n` and then count the special integers with the same number of digits as `n` but are less than or equal to `n`.
**Time:** O((log10(n))^2). The number of digits `L` is O(log10(n)). The first loop runs `L` times, and the second loop runs `L` times with an inner loop of constant size (10). The `permutations` function also takes O(L) time. This results in a very fast solution. · **Space:** O(log10(n)). We use a string to store `n` and a boolean array of size 10. The space is dominated by the string representation of `n`.
**Pros:** Extremely efficient and fast, easily passing the given constraints.; The time complexity depends only on the number of digits in `n`, not its magnitude.
**Cons:** The logic is more complex than the brute-force approach.; Requires careful handling of edge cases, like the first digit not being zero and tracking used digits.
### Explanation
Let's illustrate with `n = 135`. The string is `S = "135"` and length `L = 3`.

**Part 1: Count special numbers with length < 3**
- **1-digit numbers:** 9 (1-9).
- **2-digit numbers:** The first digit has 9 choices (1-9). The second has 9 choices (0-9, excluding the first). Total: `9 * 9 = 81`.
- Total for length < 3: `9 + 81 = 90`.

**Part 2: Count 3-digit special numbers <= 135**
- We iterate through `S = "135"`.
- **Position 0 (hundreds):** `S[0] = '1'`. We can't place a smaller digit (since it would have to be 0, which is not allowed as the first digit). So we must place '1'. Mark '1' as seen.
- **Position 1 (tens):** `S[1] = '3'`. We can place digits smaller than 3. 
  - Try `d = 0`: '0' is not seen. We form `10_`. The last digit has 8 choices (0-9, excluding 1 and 0). Add 8 to count.
  - Try `d = 2`: '2' is not seen. We form `12_`. The last digit has 8 choices. Add 8 to count.
  - Now, we must place '3'. Mark '3' as seen.
- **Position 2 (ones):** `S[2] = '5'`. We can place digits smaller than 5.
  - Try `d = 0, 2, 4` (1 and 3 are seen). For each, we form `130`, `132`, `134`. These are 3 numbers. Add 3 to count.
- The loop finishes. Since `135` itself has distinct digits, we add 1 for it.
- Total for 3-digit numbers: `8 + 8 + 3 + 1 = 20`.

**Grand Total:** `90 + 20 = 110`.

Here is the code for this approach:
```java
class Solution {
    public int countSpecialNumbers(int n) {
        String s = String.valueOf(n);
        int L = s.length();
        int res = 0;

        // Count special numbers with length < L
        for (int d = 1; d < L; d++) {
            res += 9 * permutations(9, d - 1);
        }

        // Count special numbers with length L and <= n
        boolean[] seen = new boolean[10];
        for (int i = 0; i < L; i++) {
            int digit = s.charAt(i) - '0';
            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {
                if (!seen[d]) {
                    res += permutations(10 - (i + 1), L - 1 - i);
                }
            }
            if (seen[digit]) {
                return res; // Duplicate digit found in n's prefix
            }
            seen[digit] = true;
        }

        // If we reach here, n itself is a special number
        res++;
        return res;
    }

    // Calculates P(m, n) = m! / (m-n)!
    private int permutations(int m, int n) {
        if (n > m) return 0;
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= (m - i);
        }
        return res;
    }
}
```
### Algorithm
The problem is to count special numbers up to `n`. This can be solved using digit dynamic programming and combinatorics. Let `S` be the string representation of `n` and `L` be its length.

The count is divided into two parts:
1.  **Count special numbers with fewer digits than `n`:**
    - Iterate for each length `d` from 1 to `L-1`.
    - For a `d`-digit number, the first digit has 9 choices (1-9). The remaining `d-1` digits are a permutation of `d-1` digits chosen from the 9 remaining available digits (0-9 excluding the first digit).
    - The count for length `d` is `9 * P(9, d-1)`, where `P(m, k)` is the number of k-permutations of m.
    - Sum these counts for all `d < L`.

2.  **Count special numbers with the same number of digits as `n` and are less than or equal to `n`:**
    - Iterate through the digits of `n` from left to right (index `i` from 0 to `L-1`).
    - Maintain a set of digits `seen` in the prefix.
    - At each position `i`, consider placing a digit `d` that is smaller than the digit `n[i]`.
    - For each such valid `d` (not 0 for the first position and not in `seen`), the remaining `L-1-i` positions can be filled in `P(10 - (i+1), L-1-i)` ways. Add this to the total count.
    - After checking smaller digits, check the digit `n[i]` itself. If `n[i]` is already in `seen`, it means `n` and any other number with this prefix is not special. We must stop and return the current count.
    - If `n[i]` is not in `seen`, add it to `seen` and proceed to the next position `i+1`.

3.  **Final check for `n`:**
    - If the loop completes, it means `n` itself is a special number. Increment the final count by 1.

# Solutions
### Java

```java
class Solution { public int countSpecialNumbers ( int n ) { List < Integer > digits = new ArrayList <>(); while ( n != 0 ) { digits . add ( n % 10 ); n /= 10 ; } int m = digits . size (); int ans = 0 ; for ( int i = 1 ; i < m ; ++ i ) { ans += 9 * A ( 9 , i - 1 ); } boolean [] vis = new boolean [ 10 ]; for ( int i = m - 1 ; i >= 0 ; -- i ) { int v = digits . get ( i ); for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) { if ( vis [ j ]) { continue ; } ans += A ( 10 - ( m - i ), i ); } if ( vis [ v ]) { break ; } vis [ v ] = true ; if ( i == 0 ) { ++ ans ; } } return ans ; } private int A ( int m , int n ) { return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 ); } }
```

### CPP

```cpp
class Solution { public: int countSpecialNumbers ( int n ) { int ans = 0 ; vector < int > digits ; while ( n ) { digits . push_back ( n % 10 ); n /= 10 ; } int m = digits . size (); vector < bool > vis ( 10 ); for ( int i = 1 ; i < m ; ++ i ) { ans += 9 * A ( 9 , i - 1 ); } for ( int i = m - 1 ; ~ i ; -- i ) { int v = digits [ i ]; for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) { if ( ! vis [ j ]) { ans += A ( 10 - ( m - i ), i ); } } if ( vis [ v ]) { break ; } vis [ v ] = true ; if ( i == 0 ) { ++ ans ; } } return ans ; } int A ( int m , int n ) { return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 ); } };
```

### Python

```python
class Solution : def countSpecialNumbers ( self , n : int ) -> int : def A ( m , n ): return 1 if n == 0 else A ( m , n - 1 ) * ( m - n + 1 ) vis = [ False ] * 10 ans = 0 digits = [ int ( c ) for c in str ( n )[:: - 1 ]] m = len ( digits ) for i in range ( 1 , m ): ans += 9 * A ( 9 , i - 1 ) for i in range ( m - 1 , - 1 , - 1 ): v = digits [ i ] j = 1 if i == m - 1 else 0 while j < v : if not vis [ j ]: ans += A ( 10 - ( m - i ), i ) j += 1 if vis [ v ]: break vis [ v ] = True if i == 0 : ans += 1 return ans
```