We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Count Numbers with Unique Digits

Difficulty: Medium

Problem Description

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

Key Insights

Numbers with unique digits can be formed by ensuring no digit is repeated.
For n = 0, the only valid number is 0, so the count is 1.
For n = 1, all digits from 0 to 9 are valid, resulting in 10 unique numbers.
For n >= 2, the count must avoid numbers with repeated digits, which involves combinatorial calculations based on available digits.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a combinatorial approach. We can calculate the number of valid numbers based on the number of digits.

For n = 0, return 1 as the only number is 0.
For n = 1, return 10 for numbers from 0 to 9.
For n >= 2:
- Calculate the count of valid numbers by iterating from 2 to n.
- For each digit position, calculate the number of choices:
  - The first digit can be any digit from 1 to 9 (9 choices).
  - The subsequent digits can be chosen from the remaining digits (10 - already chosen).
- Use the product of choices for each digit position to get the total count.

This approach avoids generating all numbers and focuses on counting valid configurations.

Code Solutions

def countNumbersWithUniqueDigits(n):
    if n == 0:
        return 1
    if n == 1:
        return 10
    
    count = 10  # For n = 1
    unique_digits = 9  # Choices for the first digit (1-9)
    available_digits = 9  # Choices for subsequent digits (0-9 excluding chosen)

    for i in range(2, n + 1):
        count += unique_digits * available_digits
        unique_digits -= 1
        available_digits -= 1

    return count

← Back to All Questions