Problem Description

Given two positive integers a and b, you need to count how many numbers in the range [a, b] (inclusive) have all unique digits.

A number has unique digits if no digit appears more than once in that number. For example:

• 123 has unique digits (each digit 1, 2, 3 appears exactly once)
• 112 does not have unique digits (digit 1 appears twice)
• 9876 has unique digits (each digit appears exactly once)

The solution uses digit dynamic programming with state compression. The approach calculates the count by finding all valid numbers from 1 to b with unique digits, then subtracting all valid numbers from 1 to a-1.

The key technique involves:

• Using a bitmask to track which digits (0-9) have already been used in the current number being formed
• The recursive function dfs(pos, mask, limit) where:
  • pos: current digit position being processed
  • mask: bitmask representing which digits have been used (bit i is set if digit i has been used)
  • limit: whether we're constrained by the upper bound at the current position
• For each position, we try placing digits 0-9 (respecting the limit) and skip any digit that's already been used (checked via the bitmask)
• Special handling for leading zeros: they don't count as "used" digits until we encounter the first non-zero digit

The final answer is computed as f(b) - f(a-1) where f(n) counts numbers with unique digits from 1 to n.

Intuition

When we need to count numbers with a specific property in a range [a, b], a common technique is to transform it into counting from [1, b] minus counting from [1, a-1]. This simplifies our problem to just counting valid numbers up to a given limit.

The challenge is efficiently counting all numbers up to n that have unique digits. A naive approach would be to check each number individually, but this would be too slow for large ranges.

The key insight is that we can build valid numbers digit by digit from left to right. As we construct each number, we need to track which digits we've already used to ensure uniqueness. This naturally leads to using a bitmask - if we've used digit 3, we set bit 3 in our mask; if we've used digit 7, we set bit 7, and so on.

Why digit DP? When building numbers digit by digit, we notice that many subproblems repeat. For instance, if we're building a 5-digit number and we've filled the first 3 positions with certain digits, the count of valid ways to fill the remaining 2 positions depends only on:

• Which digits we've already used (captured by the mask)
• Whether we're still bounded by the original number's digits (the limit flag)
• The current position we're filling

This observation allows us to memoize our results and avoid redundant calculations.

The limit flag is crucial for correctness. When building a number up to, say, 523, if we've placed 5 in the first position and 2 in the second position, then the third position can only go up to 3. But if we had placed 4 in the first position, then all subsequent positions could use any digit from 0-9 (respecting uniqueness). This is why we track whether we're still "hugging" the upper bound.

Leading zeros require special attention. The number 0123 is actually just 123, so the leading 0 shouldn't count as a "used" digit. We handle this by keeping the mask at 0 until we place our first non-zero digit, effectively ignoring leading zeros in our uniqueness check.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution implements digit DP with state compression using a recursive memoized function. Here's how the implementation works:

Main Function Structure: The numberCount function calculates the result using the difference formula: f(b) - f(a-1). It processes each bound by converting it to a string and calling the digit DP function.

Core DP Function - dfs(pos, mask, limit):

The recursive function has three parameters:

• pos: Current digit position being processed (0 for leftmost digit)
• mask: Bitmask tracking which digits (0-9) have been used
• limit: Boolean indicating if we're constrained by the upper bound

Base Case:

if pos >= len(num):
    return 1 if mask else 0

When we've processed all positions, we return 1 if we've formed a valid number (mask ≠ 0, meaning it's not all leading zeros), otherwise 0.

Recursive Case:

1. Determine the upper bound for current digit:

   up = int(num[pos]) if limit else 9

   If limit is True, we can only use digits up to num[pos]. Otherwise, we can use any digit 0-9.

2. Try each possible digit:

   for i in range(up + 1):
       if mask >> i & 1:
           continue

   We iterate through possible digits, skipping any that have already been used (checked by testing if bit i is set in the mask).

3. Handle leading zeros:

   nxt = 0 if mask == 0 and i == 0 else mask | 1 << i

   If the mask is 0 (no non-zero digits yet) and we're placing a 0, keep the mask as 0 (treating it as a leading zero). Otherwise, set the bit corresponding to digit i.

4. Recursive call:

   ans += dfs(pos + 1, nxt, limit and i == up)

   Move to the next position with the updated mask. The limit remains True only if it was True before AND we chose the maximum possible digit.

Memoization: The @cache decorator automatically memoizes the function results, preventing redundant calculations for identical states.

Computing the Final Answer:

num = str(a - 1)
x = dfs(0, 0, True)
dfs.cache_clear()
num = str(b)
y = dfs(0, 0, True)
return y - x

1. Calculate count for numbers from 1 to a-1
2. Clear the cache (important since we're reusing the same function with different num)
3. Calculate count for numbers from 1 to b
4. Return the difference to get the count in range [a, b]

The time complexity is O(D × 2^10 × 2) where D is the number of digits, as we have at most D positions, 2^10 possible masks, and 2 possible values for the limit flag.

Example Walkthrough

Let's walk through counting numbers with unique digits in the range [10, 25].

Step 1: Transform the problem

• We need to find: f(25) - f(9)
• This counts all valid numbers from 1 to 25, then subtracts valid numbers from 1 to 9

Step 2: Calculate f(9)

Building numbers up to 9 digit by digit:

• Position 0 (only position), limit=True, mask=0 (no digits used yet)
• We can place digits 0-9 (but limited by 9)
  • Place 0: mask stays 0 (leading zero), contributes 0
  • Place 1: mask becomes 0000000010 (bit 1 set), contributes 1
  • Place 2: mask becomes 0000000100 (bit 2 set), contributes 1
  • ... continues for 3,4,5,6,7,8,9
• Result: f(9) = 9 (the numbers 1,2,3,4,5,6,7,8,9 all have unique digits)

Step 3: Calculate f(25)

Building 2-digit numbers up to 25:

Starting with dfs(0, 0, True) for "25":

• Position 0 (tens place), limit=True, mask=0
  • Try digit 0: mask stays 0 (leading zero)
    • Position 1, limit=False, mask=0
    • Can place 1-9 (not 0 since mask=0), each valid → contributes 9
  • Try digit 1: mask=0000000010
    • Position 1, limit=False, mask=0000000010
    • Can place 0,2,3,4,5,6,7,8,9 (not 1) → contributes 9
  • Try digit 2: mask=0000000100
    • Position 1, limit=True (since 2=upper bound), mask=0000000100
    • Can only place 0,1,3,4,5 (limited by 5, can't use 2)
    • Contributes 5

Total for f(25):

• From digit 0 in tens place: 9 (numbers 01-09, which are really 1-9)
• From digit 1 in tens place: 9 (numbers 10,12,13,14,15,16,17,18,19)
• From digit 2 in tens place: 5 (numbers 20,21,23,24,25)
• f(25) = 9 + 9 + 5 = 23

Step 4: Final answer

• Count in [10, 25] = f(25) - f(9) = 23 - 9 = 14

The valid numbers are: 10,12,13,14,15,16,17,18,19,20,21,23,24,25 (exactly 14 numbers)

Note how the algorithm efficiently handles:

• Leading zeros: When placing 0 in the tens place, mask stays 0, allowing all digits in the ones place
• Limit flag: When we place 2 in tens place (matching the upper bound), we're limited to digits 0-5 in ones place
• Bitmask tracking: Each used digit sets its corresponding bit, preventing reuse

Solution Implementation

Time and Space Complexity

The time complexity is O(m × 2^10 × 10), where m is the number of digits in b.

This complexity arises from:

• m: The recursion depth equals the number of digit positions we need to process (length of the number string)
• 2^10: The mask parameter can have at most 2^10 different states since we're tracking which digits (0-9) have been used via a bitmask
• 10: At each position, we iterate through at most 10 possible digit choices (0-9)

The space complexity is O(m × 2^10).

This complexity comes from:

• The memoization cache stores results for unique combinations of (pos, mask, limit) parameters
• pos can have m different values (0 to m-1)
• mask can have at most 2^10 different values (representing all possible combinations of used digits)
• limit is a boolean with 2 possible values
• The total number of cached states is bounded by O(m × 2^10 × 2) = O(m × 2^10)
• Additionally, the recursion stack depth is O(m), but this is dominated by the cache storage

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Clear Cache Between Function Calls

One critical pitfall is reusing the memoized function without clearing the cache between different upper bounds. Since the digit_dp function uses the outer variable upper_bound, the cached results from one call become invalid when processing a different number.

Incorrect Implementation:

def numberCount(self, a: int, b: int) -> int:
    @cache
    def digit_dp(position, mask, is_tight):
        # ... implementation ...
      
    # First call with a-1
    upper_bound = str(a - 1)
    count_below_a = digit_dp(0, 0, True)
  
    # Second call with b - WRONG! Cache still has results from a-1
    upper_bound = str(b)
    count_up_to_b = digit_dp(0, 0, True)
  
    return count_up_to_b - count_below_a

Solution: Always clear the cache between calls or use separate function instances:

# Option 1: Clear cache explicitly
digit_dp.cache_clear()

# Option 2: Create separate function instances
def create_counter(upper_bound):
    @cache
    def digit_dp(position, mask, is_tight):
        # ... implementation ...
    return digit_dp(0, 0, True)

2. Incorrect Handling of Leading Zeros

A common mistake is treating leading zeros as "used digits" which would prevent valid numbers like 102 (where 0 appears after non-zero digits).

Incorrect Implementation:

# Wrong: Always marks digit as used, even for leading zeros
next_mask = used_digits_mask | (1 << digit)

Solution: Only mark zeros as used when they appear after the first non-zero digit:

if used_digits_mask == 0 and digit == 0:
    next_mask = 0  # Still in leading zeros
else:
    next_mask = used_digits_mask | (1 << digit)

3. Off-by-One Error in Range Calculation

When calculating numbers in range [a, b], forgetting to subtract 1 from a leads to excluding a itself from the count.

Incorrect Implementation:

# Wrong: This counts numbers in range [a+1, b]
count_below_a = count_unique_digit_numbers(str(a))
count_up_to_b = count_unique_digit_numbers(str(b))
return count_up_to_b - count_below_a

Solution: Use a-1 as the lower bound:

count_below_a = count_unique_digit_numbers(str(a - 1))
count_up_to_b = count_unique_digit_numbers(str(b))
return count_up_to_b - count_below_a

4. Incorrect Base Case Return Value

Returning 1 unconditionally at the base case counts numbers consisting only of leading zeros as valid.

Incorrect Implementation:

if position >= len(upper_bound):
    return 1  # Wrong: counts "000" as valid

Solution: Check if at least one non-zero digit was used:

if position >= len(upper_bound):
    return 1 if used_digits_mask else 0

5. Not Propagating the Tight Constraint Correctly

The tight constraint should only remain true if we chose the maximum possible digit at the current position.

Incorrect Implementation:

# Wrong: Always passes the same tight value
digit_dp(position + 1, next_mask, is_tight)

Solution: Update tight constraint based on the chosen digit:

digit_dp(position + 1, next_mask, is_tight and (digit == max_digit))