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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Numbers with Unique Digits

Number: 357

Difficulty: Medium

Paid? No

Companies: Google, J.P. Morgan, Apple

Problem Description

Given a non-negative integer n, count all numbers x with unique digits such that 0 <= x < 10^n. This involves ensuring that no digit repeats within a number.

Key Insights

  • Use combinatorial counting to determine the number of valid numbers of a given digit length.
  • For numbers with more than one digit, the first digit cannot be zero.
  • For each additional digit, the choices decrease because digits must remain unique.
  • The solution adds up valid counts for each possible digit length from 1 to n, plus the number 0.

Space and Time Complexity

Time Complexity: O(n) per computation since we iterate at most 10 times (n <= 8). Space Complexity: O(1) as only a few variables are used.

Solution

The solution uses a combinatorial approach. For n = 0, the answer is 1 (only number 0). For n >= 1, the solution counts valid numbers for each digit length k (1 <= k <= n):

  1. For 1-digit numbers, there are 9 possibilities (1-9).
  2. For k-digit numbers (k > 1), the first digit has 9 possibilities (1-9), and each subsequent digit has a decreasing number of available digits (from 10 minus the number already used). Specifically, for the second digit there are 9 choices, for the third digit there are 8, and so forth.
  3. Sum the counts for each valid digit length and add 1 for the number 0. This approach avoids generating all numbers and leverages basic combinatorial principles for an efficient count.

Code Solutions

# Define the function to count numbers with unique digits
def countNumbersWithUniqueDigits(n):
    # For n = 0, only number valid is 0.
    if n == 0:
        return 1

    # Initialize result with one count for '0'
    result = 1

    # For numbers with more than 0 digits, iterate through digit lengths 1 to n (max 10 digits)
    for k in range(1, min(n, 10) + 1):
        # Start with 9 options for the first digit (1 through 9)
        unique_count = 9
        # For remaining digits, each digit's options reduce as digits are used
        for j in range(1, k):
            unique_count *= (10 - j)
        # Add count for k-digit numbers to result
        result += unique_count

    return result

# Example usage:
n = 2
print(countNumbersWithUniqueDigits(n))  # Expected output: 91

# You can test other cases by calling countNumbersWithUniqueDigits with different n values.
← Back to All Questions