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 * 109Problem Overview: Given an integer n, count how many numbers in the range [1, n] have all digits distinct. Any number containing repeated digits (like 11 or 232) is excluded. The challenge is efficiently counting valid numbers without checking every integer up to n.
Approach 1: Backtracking Enumeration (Time: O(10!), Space: O(10))
This approach generates numbers with unique digits using backtracking. Start from digits 1-9, track used digits with a boolean array, and recursively append unused digits. Stop exploring once the constructed number exceeds n. Each recursive step tries digits 0-9 that haven't been used, ensuring the number maintains the distinct-digit property.
The key insight is pruning early: if the current number is already greater than n, the branch stops immediately. This avoids scanning every number up to n. The search tree is bounded by permutations of digits (at most 10 levels). This method clearly shows the structure of valid numbers and is easy to reason about, but it becomes less elegant compared to direct counting.
Approach 2: Counting by Digit Positions (Digit Combinatorics) (Time: O(d * 10), Space: O(1))
The optimal approach counts valid numbers digit by digit instead of generating them. Let d be the number of digits in n. First count all valid numbers with fewer digits using permutation formulas. For example, for length k, the first digit has 9 choices (1-9), and remaining digits use permutations of unused digits.
Then process numbers with the same length as n. Iterate through each digit from left to right. For each position, count how many smaller digits can be placed there that haven't been used before, and multiply by the permutations of remaining digits. Maintain a set of used digits; if a digit repeats, the process stops because further prefixes would contain duplicates.
This method is essentially a combinatorics-driven form of digit DP. Instead of exploring every number, it directly counts how many valid permutations fit under the prefix constraint of n. The runtime depends only on the number of digits in n, making it extremely efficient.
Key concepts include permutation counting from math, prefix constraints from dynamic programming, and digit-level enumeration techniques commonly used in digit DP problems.
Recommended for interviews: The digit-position counting approach is what most interviewers expect. It shows strong understanding of combinatorics and prefix constraints. The backtracking solution demonstrates the idea of generating unique-digit numbers, but the counting method proves you can convert enumeration into a mathematical count with optimal complexity.
This approach involves using backtracking to explore all possible numbers with distinct digits. For each number, check the digits and ensure they are unique.
It is efficient for smaller n but still performs well for given constraints due to digit limitations.
Here, the countSpecialNumbers function calculates the number of special integers less than or equal to n. It uses combinations of the digits, ensures uniqueness by checking seen digits, and adds permutations for counting possible numbers.
Time Complexity: O(d!) where d is the number of digits in n; it effectively handles permutations.
Space Complexity: O(d) for the recursion stack and seen digits storage.
This approach counts special numbers by evaluating the number at each digit position in terms of possible values. Precalculate special numbers for known lengths and multiply permutations iterating over valid digits.
The JavaScript implementation uses factorial function for permutations and Set for tracking already used digits to ensure the specialness of the number.
JavaScript
C#
Time Complexity: O(d!) as it assesses permutations.
Space Complexity: O(d) for the Set tracking and string manipulation.
This problem essentially asks for the number of numbers in the given range [l, ..r] that satisfy certain conditions. The conditions are related to the composition of the numbers rather than their size, so we can use the concept of Digit DP to solve it. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, ..r] problem, we generally convert it to the problem of [1, ..r] and then subtract the result of [1, ..l - 1], i.e.:
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
However, for this problem, we only need to find the value for the range [1, ..n].
Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.
Based on the problem information, we design a function dfs(i, mask, lead, limit), where:
represents the current position being searched, starting from the highest digit, i.e., i = 0 represents the highest digit. represents the current state of the number, i.e., the j-th bit of mask being 1 indicates that the digit j has been used. indicates whether the current number only contains leading 0s. indicates whether the current number is restricted by the upper bound.The function executes as follows:
If i exceeds the length of the number n, it means the search is over. If lead is true, it means the current number only contains leading 0s, so return 0. Otherwise, return 1.
If limit is false and lead is false and the state of mask has been memoized, directly return the memoized result.
Otherwise, we calculate the current upper bound up. If limit is true, up is the i-th digit of the current number. Otherwise, up = 9.
Then we iterate over [0, up]. For each digit j, if the j-th bit of mask is 1, it means the digit j has been used, so we skip it. Otherwise, if lead is true and j = 0, it means the current number only contains leading 0s, so we recursively search the next digit. Otherwise, we recursively search the next digit and update the state of mask.
Finally, if limit is false and lead is false, memoize the current state.
Return the final answer.
The time complexity is O(m times 2^D times D), and the space complexity is O(m times 2^D). Here, m is the length of the number n, and D = 10$.
Similar Problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(d!) where d is the number of digits in n; it effectively handles permutations. Space Complexity: O(d) for the recursion stack and seen digits storage. |
| Counting by Digit Positions | Time Complexity: O(d!) as it assesses permutations. Space Complexity: O(d) for the Set tracking and string manipulation. |
| State Compression + Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(10!) worst case | O(10) | Useful for understanding how unique-digit numbers are formed or when demonstrating recursive generation techniques |
| Counting by Digit Positions (Combinatorics / Digit DP) | O(d * 10) | O(1) | Best for interviews and large inputs; avoids enumeration by counting valid permutations under prefix constraints |
2376. Count Special Integers | Leetcode Weekly Contest 306 | LeetCode 2376 • Bro Coders • 3,485 views views
Watch 9 more video solutions →Practice Count Special Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor