Count Numbers With Unique Digits II

Count Numbers With Unique Digits II

What is this problem about?

Building on the classic "unique digits" problem, "Count Numbers With Unique Digits II" usually asks you to count unique-digit numbers within a specific range $[L, R]$. Unlike the original version which starts from zero, this variation requires you to handle arbitrary bounds. A number is valid if no two digits in its decimal representation are the same.

Why is this asked in interviews?

Amazon and other companies ask this to test your ability to move from a general mathematical formula to a range-based query. It evaluates whether you can use a brute-force approach for small ranges or if you can apply "Prefix Counting" logic (Count(R) - Count(L-1)) using a more efficient algorithm like Digit DP.

Algorithmic pattern used

For smaller ranges, simple Iterative Simulation with a Hash Set or boolean array is sufficient. For each number in the range, you extract its digits and check for duplicates. For larger ranges, the standard pattern is Digit Dynamic Programming (Digit DP). In Digit DP, you maintain a bitmask of "used digits" as you build the number from left to right, ensuring you never pick a digit that is already in the mask.

Example explanation

Range: [80, 120]

• Brute force check:
  • 80: {8, 0} (Unique)
  • 81: {8, 1} (Unique)
  • ...
  • 100: {1, 0, 0} (Not unique)
  • 111: {1, 1, 1} (Not unique)
  • 120: {1, 2, 0} (Unique) You would count all such numbers where the set of digits has the same size as the number of digits.

Common mistakes candidates make

A common mistake is not correctly handling the "leading zero" case in a Digit DP approach, which can lead to incorrect counts for numbers with fewer digits than the maximum bound. In the simulation approach, candidates often forget to reset their "seen" set for each new number.

Interview preparation tip

Practice the bitmask-based Digit DP template. It is a powerful tool that solves almost all "count numbers with property X in range [L, R]" problems. Understanding how to use a mask to track used digits is a key component of this pattern.