{x}
blog image

Count Numbers with Unique Digits

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.

 

Example 1:

Input: n = 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

Example 2:

Input: n = 0
Output: 1

 

Constraints:

  • 0 <= n <= 8

Solution Explanation: Count Numbers with Unique Digits

This problem asks to count the numbers with unique digits within the range [0, 10^n). A naive approach would be to iterate through all numbers and check for uniqueness, but this is inefficient for larger n. A more efficient solution uses dynamic programming or a recursive approach with memoization.

Approach: Dynamic Programming with Memoization

The core idea is to build up the count recursively, digit by digit. We maintain a bitmask (mask) to track which digits have already been used.

State:

  • i: The current digit position (starting from the most significant digit, index 0).
  • mask: A bitmask representing used digits (1 bit for each digit 0-9). If the j-th bit is set, digit j has been used.
  • lead: A boolean indicating whether we are still dealing with leading zeros.

Recursion:

The recursive function dfs(i, mask, lead) counts the numbers with unique digits for the remaining i digits:

  1. Base Case: If i is negative (all digits processed), return 1 (we have a valid number).

  2. Recursive Step: Iterate through digits j from 0 to 9.

    • If the j-th bit is set in mask, skip it (digit already used).
    • If lead is true and j is 0, recursively call dfs with lead remaining true (we can have multiple leading zeros).
    • Otherwise, recursively call dfs with the j-th bit set in the mask and lead set to false (leading zero situation handled).
    • Accumulate the results from the recursive calls.

  3. Memoization: Store the results of dfs(i, mask, lead) to avoid redundant calculations. This significantly improves efficiency.

Initial Call:

The initial call is dfs(n - 1, 0, true), starting with the highest digit position (n-1) and an empty mask.

Time and Space Complexity Analysis

  • Time Complexity: O(10n). Although the recursion explores a large space, memoization drastically reduces the time, as each (i, mask, lead) state is computed only once. The dominant factor is the number of possible bitmask combinations, approximately 210, which is constant. The number of recursive calls is bounded by the number of possible states, which is polynomial in n.

  • Space Complexity: O(10n). The space used by memoization is proportional to the number of unique (i, mask, lead) states. Again, memoization makes the space complexity less than it would be without it. In practice, the space complexity is dominated by the memoization table.

Code Examples

The code examples in Python, Java, C++, Go, and TypeScript all implement this recursive approach with memoization. The structure is very similar across languages; the key differences lie in syntax and data structure implementations (e.g., memoization using @cache in Python vs. a 2D array in other languages). The core logic remains the same.