algoadvance

Leetcode 357. Count Numbers with Unique Digits

Problem Statement

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

Clarifying Questions

1. What is the maximum value of n we should consider?
   • For the problem constraints, usually, 0 <= n <= 10.
2. Should we account for numbers with leading zeros?
   • No, since leading zeros do not represent valid numbers in decimal notation.
3. Should we include single-digit numbers in the count?
   • Yes, single-digit numbers (0 through 9) should be included in the count if n >= 1.

Strategy

1. Base case handling:
   • When n = 0, there is only one number (0).
2. General case:
   • For n = 1, there are 10 numbers (0 through 9), all of which are unique.
   • For n = 2, we need to count numbers from 0 to 99 with unique digits.
     • This involves choosing digits for each place ensuring no repeats.
   • For higher n, we generalize using permutation principles:
     • The first digit has 9 options (1-9).
     • The second digit has 9 remaining options (0, 2-9 if the first is 1).
     • The third digit has 8 options, etc.
   • Compute the sum iteratively for each valid configuration up to n.

Code

#include <iostream>

int countNumbersWithUniqueDigits(int n) {
    if (n == 0) {
        return 1;
    }
    
    int unique_count = 10; // For n = 1, 0 to 9.
    int available_digits = 9; // Digits left to use for each new place
    int current_count = 9; // Remaining unique numbers to place for each position

    int max_digits = std::min(n, 10); // Since 10! has only 10 digits.
    
    for (int i = 2; i <= max_digits; ++i) {
        current_count *= available_digits;
        unique_count += current_count;
        --available_digits;
    }

    return unique_count;
}

int main() {
    int n = 2; // Example input
    int result = countNumbersWithUniqueDigits(n);
    std::cout << "Count of numbers with unique digits for n = " << n << " is: " << result << std::endl;
    return 0;
}

Time Complexity

• The runtime complexity of this solution is (O(1)) because the loop runs at most up to 10 times regardless of the specific input value of n.
• Space complexity is (O(1)) as well, since we are using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?