Skip to main content
Talentd

Count Numbers With Unique Digits II - Solution & Explanation

EasyPremiumFree on FleetCodeHash TableMathDynamic Programming13 min readAsked at: Amazon
Practice this problem

Problem Statement

Given two positive integers 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 <= 1000

Approach Overview

Problem 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.

Approach 1: State Compression + Digit DP

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:

  1. We convert the number n into a string num, where num[0] is the highest digit and num[len - 1] is the lowest digit.
  2. Based on the problem information, we design a function 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
State Compression + Digit DP—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Enumeration with Hash SetO(n * d)O(d)Small ranges where iterating each number is cheap and quick to implement
State Compression + Digit DPO(d * 2^10 * 10)O(d * 2^10)Large ranges or interview scenarios requiring efficient counting without scanning every number

Video Solution

3032. Count Numbers With Unique Digits II (Leetcode Easy) • Programming Live with Larry • 597 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Numbers With Unique Digits II easy or hard?
LeetCode classifies this problem as Easy, mainly because the digit length is small and brute-force checking is straightforward. However, recognizing and implementing the Digit DP optimization requires familiarity with advanced dynamic programming patterns.
Count Numbers With Unique Digits II Python/Java solution
Most implementations use digit DP with memoization. The algorithm recursively builds digits, maintains a bitmask of used digits, and respects a tight upper bound constraint. The same logic works across Python, Java, C++, Go, and TypeScript with only syntax differences.
How to solve Count Numbers With Unique Digits II in O(n)?
A simple approach iterates from a to b and checks whether each number has repeated digits. Convert the number to digits and track seen digits using a set or boolean array. Each check costs O(d), giving overall complexity O(n * d). This method is easy to implement but inefficient for large ranges.
What is the best approach for Count Numbers With Unique Digits II?
The most efficient approach uses Digit Dynamic Programming with state compression. A 10-bit mask tracks which digits have been used, and a tight constraint ensures the generated number does not exceed the bound. Compute count(b) minus count(a − 1) to handle ranges. The complexity is about O(d * 2^10 * 10), where d is the number of digits.
Is Count Numbers With Unique Digits II asked at Google/Amazon/Meta?
Digit DP and unique-digit counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include counting numbers with digit constraints or without repeated digits within a range. This problem tests familiarity with digit-based dynamic programming and bitmask states.
What data structure is used in Count Numbers With Unique Digits II?
The brute-force solution uses a hash set or boolean array to detect duplicate digits. The optimized solution relies on a bitmask to represent used digits, combined with memoization in dynamic programming. This state compression technique efficiently tracks digit usage during recursion.
What is the time complexity of Count Numbers With Unique Digits II?
The optimal Digit DP solution runs in O(d * 2^10 * 10) time and O(d * 2^10) space. Since d is at most 10, the algorithm is effectively constant time for practical inputs. A naive enumeration approach takes O(n * d) time where n is the size of the range.

Ready to solve this problem?

Practice Count Numbers With Unique Digits II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Numbers with Unique Digits