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.

Description Hints 1 Solution Video 4:54

3032. Count Numbers With Unique Digits II

Easy87.4% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

You can traverse over all numbers and check if the current number has unique digits or not.

4:54

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution