algoadvance

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

Example:

Input: n = 2
Output: 91

Explanation: The total numbers with unique digits, x, where 0 ≤ x < 10^2, are [0, 1, 2, ..., 99]. Among these, 91 have unique digits.

Clarifying Questions

  1. What is the range of n?
    • Typically, 0 ≤ n ≤ 8 because 10^9 is the highest possible valid number within the 32-bit integer range.
  2. What should be the output if n is 0?
    • The output should be 1, since the only number in the range 0 ≤ x < 10^0 is 0 itself.
  3. Are there constraints on the runtime or memory usage?
    • No specific constraints mentioned, but an optimal solution is preferred.

Strategy

  1. Base Cases:
    • If n = 0, return 1.
    • If n = 1, return 10, since we have numbers 0 to 9, all of which are unique.
  2. Recursive Calculation:
    • Use a backtracking or combinatorial approach to calculate the numbers with unique digits for higher values of n.
    • Start with the digit selection process for each additional digit position until reaching n.
    • Use the principle of counting permutations with constraints (where the constraint is that digits must be unique).

Code

def countNumbersWithUniqueDigits(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 10
    
    # Dynamic Programming storage for the calculation
    unique_count = [0] * (n+1)
    unique_count[0] = 1
    unique_count[1] = 10
    
    # Calculate for values 2 to n
    for i in range(2, n + 1):
        count = 9
        for j in range(i-1):
            count *= (9 - j)
        unique_count[i] = unique_count[i-1] + count
    
    return unique_count[n]

# Usage example:
n = 2
print(countNumbersWithUniqueDigits(n))  # Output: 91

Time Complexity

The time complexity of this solution is O(n):

Given that the loop runs a fixed number of multiplications (at most 9 for any n), this is efficient.

The space complexity is also O(n) for the unique_count list, which stores the results for 0 to n.

Try our interview co-pilot at AlgoAdvance.com