a and b, return the count of numbers having unique digits in the range [a, b] (inclusive).
Example 1:
Input: a = 1, b = 20 Output: 19 Explanation: All the numbers in the range [1, 20] have unique digits except 11. Hence, the answer is 19.
Example 2:
Input: a = 9, b = 19 Output: 10 Explanation: All the numbers in the range [9, 19] have unique digits except 11. Hence, the answer is 10.
Example 3:
Input: a = 80, b = 120 Output: 27 Explanation: There are 41 numbers in the range [80, 120], 27 of which have unique digits.
Constraints:
1 <= a <= b <= 1000Problem Overview: Given two integers a and b, count how many numbers in the inclusive range [a, b] contain only unique digits. A number is valid if no digit repeats inside its decimal representation.
Approach 1: Direct Enumeration with Hash Set (O(n * d) time, O(d) space)
The straightforward approach iterates through every number from a to b. For each number, convert it to digits and track seen digits using a set or boolean array. If a digit repeats, the number is invalid; otherwise increment the count. This solution relies on simple Hash Table style membership checks for duplicate detection. The digit length d is at most 10, so validation per number is cheap. However, the runtime becomes slow when the range size grows large because every number must be inspected.
Approach 2: State Compression + Digit DP (O(d * 2^10 * 10) time, O(d * 2^10) space)
The optimal approach counts valid numbers without enumerating the entire range. Use digit dynamic programming to build numbers digit by digit while tracking which digits are already used. A 10‑bit mask represents used digits; bit i indicates whether digit i has appeared. The DP state typically includes the current index, the mask, and a tight flag indicating whether the prefix is still constrained by the upper bound. Each transition tries digits 0–9 that are not yet set in the mask. This technique falls under Dynamic Programming and leverages bitmask state compression from Math and combinatorics.
To handle ranges, compute count(b) and subtract count(a - 1). The DP effectively explores only digit combinations, not every integer. Since the mask has 2^10 possibilities and digit length is small (≤10), the complexity stays tiny and independent of the numeric range size.
Recommended for interviews: Start with the enumeration idea to show you understand the constraint (checking repeated digits). Interviewers usually expect the digit DP optimization because it scales to very large ranges. Implementing the bitmask state and tight constraint demonstrates strong understanding of digit-based DP patterns commonly used in counting problems.
The problem asks to count how many numbers in the range [a, b] have unique digits. We can solve this problem using state compression and digit DP.
We can use a function f(n) to count how many numbers in the range [1, n] have unique digits. Then the answer is f(b) - f(a - 1).
In addition, we can use a binary number to record the digits that have appeared in the number. For example, if the digits 1, 3, 5 have appeared in the number, we can use 10101 to represent this state.
Next, we use memoization search to implement digit DP. We search from the starting point to the bottom layer to get the number of schemes, return the answer layer by layer and accumulate it, and finally get the final answer from the search starting point.
The basic steps are as follows:
n into a string num, where num[0] is the highest digit and num[len - 1] is the lowest digit.dfs(pos, mask, limit), where pos represents the current processing position, mask represents the digits that have appeared in the current number, and limit represents whether there is a limit at the current position. If limit is true, then the digit at the current position cannot exceed num[pos].The answer is dfs(0, 0, true).
The time complexity is O(m times 2^{10} times 10), and the space complexity is O(m times 2^{10}). Where m is the number of digits in b.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| State Compression + Digit DP | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Enumeration with Hash Set | O(n * d) | O(d) | Small ranges where iterating each number is cheap and quick to implement |
| State Compression + Digit DP | O(d * 2^10 * 10) | O(d * 2^10) | Large ranges or interview scenarios requiring efficient counting without scanning every number |
3032. Count Numbers With Unique Digits II (Leetcode Easy) • Programming Live with Larry • 577 views views
Watch 2 more video solutions →Practice Count Numbers With Unique Digits II with our built-in code editor and test cases.
Practice on FleetCode