Jobs

Interviews

Discussions

Count Numbers with Unique Digits

Medium

Asked by:

43 views

Topics:

Dynamic ProgrammingRecursionGreedy Algorithms

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

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

Try coding it in LeetCode

Count Numbers with Unique Digits

Medium

Asked by:

43 views

Topics:

Dynamic ProgrammingRecursionGreedy Algorithms

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

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input number n? Can n be negative or zero?
Are we counting numbers with unique digits inclusively, meaning should we include numbers from 0 up to 10^n - 1?
Are leading zeros allowed in the count (e.g., if n=2, should '01' be considered a number with unique digits)?
For n > 10, what should the return value be? Should I handle this case or is n guaranteed to be less than or equal to 10?
Could you provide a small example of the expected output for a specific value of n, such as n=2 or n=3?

Brute Force Solution

Approach

The brute force strategy is all about checking absolutely every number to see if it meets our unique digit requirement. We'll go through the numbers one by one, and for each one, we'll see if it has repeating digits.

Here's how the algorithm would work step-by-step:

Start counting from zero and go up to the largest number that has the number of digits we're allowed.
For each number, look at its digits individually.
Check if any digit appears more than once within that number.
If a number has repeating digits, discard it and move on to the next number.
If a number has only unique digits, count it as a good number.
Keep counting and checking until we reach the largest possible number with the allowed number of digits.
The total count of all the 'good' numbers we found is the answer.

Code Implementation

def count_numbers_with_unique_digits_brute_force(number_of_digits):
    if number_of_digits == 0:
        return 1

    count_of_unique_digit_numbers = 0
    maximum_number = int('9' * number_of_digits)

    for number in range(maximum_number + 1):

        # Convert the number to a string to iterate through digits
        number_as_string = str(number)
        digits_seen = set()
        is_unique = True

        for digit_character in number_as_string:
            digit = int(digit_character)

            # If we've seen this digit before, it's not a unique number
            if digit in digits_seen:
                is_unique = False
                break

            digits_seen.add(digit)

        # Only increment the count if all digits are unique
        if is_unique:

            count_of_unique_digit_numbers += 1

    return count_of_unique_digit_numbers

Big(O) Analysis

Time Complexity

O(10^n) – The algorithm iterates through all numbers from 0 up to 10^n - 1, where n is the number of digits allowed. For each number, it checks if its digits are unique. In the worst case, the digit uniqueness check takes O(n) time. Since the outer loop iterates 10^n times, and each iteration requires O(n) work, the overall time complexity is O(n * 10^n). However, since n is a small constant (0 to 10), we can approximate it by O(10^n) as the dominant factor.

Space Complexity

O(1) – The brute force approach, as described, iterates through numbers and checks for repeating digits within each number. The plain English explanation doesn't specify the usage of any auxiliary data structures like arrays, hash maps, or sets to store digits or track visited numbers. The operations appear to be performed using a fixed number of variables for checking the digits of each number, thus using constant extra space regardless of the input size N (number of digits allowed).

Optimal Solution

Approach

Instead of checking every possible number, we use a mathematical trick to count valid numbers based on the number of digits. This avoids unnecessary computations by cleverly calculating the possibilities.

Here's how the algorithm would work step-by-step:

Realize that single-digit numbers (0-9) always have unique digits, so we know we can always start with 10.
For numbers with two digits, the first digit can be any number from 1 to 9 (9 options), and the second digit can be any digit that's not the first digit (9 options). We multiply these.
For numbers with three digits, the first digit can be any number from 1 to 9 (9 options), the second digit can be any digit that's not the first digit (9 options), and the third digit can be any digit that's not the first two digits (8 options). We multiply these.
Continue this pattern: for each additional digit, the number of options for that digit decreases by one. We keep multiplying to find the valid numbers with that many digits.
Stop when the number of digits requested is reached or when the number of available unique digits (0-9) is used up.
Sum up the number of valid numbers for each possible number of digits (1 digit, 2 digits, 3 digits, etc.) to get the final result.

Code Implementation

def count_numbers_with_unique_digits(number_of_digits):
    if number_of_digits == 0:
        return 1

    available_unique_numbers = 10
    total_unique_numbers = 10
    unique_digits_product = 9

    # Account for the first digit not being zero.
    for digit in range(2, min(number_of_digits + 1, 11)):
        unique_digits_product = unique_digits_product * (available_unique_numbers - 1)
        
        # Add the result to the total
        total_unique_numbers += unique_digits_product

        available_unique_numbers -= 1

    return total_unique_numbers

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates at most 10 times because we only have 10 unique digits (0-9). The number of iterations is directly determined by the input n, but the loop terminates when either n is reached or all 10 digits are exhausted. Since the maximum number of iterations is capped at 10, regardless of the input n (as long as n > 10, the loop still runs a maximum of 10 times), the runtime is constant. Thus, the time complexity is O(1).

Space Complexity

O(1) – The provided solution uses a constant amount of extra space. It primarily involves arithmetic calculations and updating a counter variable to accumulate the total count of numbers with unique digits. No auxiliary data structures like arrays, lists, or hashmaps are used, and the depth of any implicit recursion is limited and doesn't depend on the input 'n'. Therefore, the space complexity is constant, independent of the input 'n'.

Edge Cases

Case	How to Handle
Input n = 0	Return 1 since there is one number (0) with unique digits
Input n = 1	Return 10 since there are 10 single-digit numbers (0-9) with unique digits
Input n > 10	Since there are only 10 unique digits, any number with more than 10 digits must have duplicate digits, so cap n at 10.
Integer Overflow when calculating permutations	The maximum value of n is capped at 10, so integer overflow is not a concern with reasonably sized integer types.
Large value of n up to the imposed limit (n=10)	Iterative dynamic programming is more efficient than recursion as n scales up to its maximum size, avoiding stack overflow issues.
No valid solution exists other than the explicit constraints	The problem definition always ensures a solution by defining valid input n between 0 and 10 inclusive
Negative input for n	The constraints define valid input n between 0 and 10 inclusive so we should throw an exception or return 0 for negative inputs
Non-integer input for n	Cast the input to an integer to handle floating-point or other unexpected input types

Input n = 0

How to Handle:

Return 1 since there is one number (0) with unique digits

Input n = 1

How to Handle:

Return 10 since there are 10 single-digit numbers (0-9) with unique digits

Input n > 10

How to Handle:

Since there are only 10 unique digits, any number with more than 10 digits must have duplicate digits, so cap n at 10.

Integer Overflow when calculating permutations

How to Handle:

The maximum value of n is capped at 10, so integer overflow is not a concern with reasonably sized integer types.

Large value of n up to the imposed limit (n=10)

How to Handle:

Iterative dynamic programming is more efficient than recursion as n scales up to its maximum size, avoiding stack overflow issues.

No valid solution exists other than the explicit constraints

How to Handle:

The problem definition always ensures a solution by defining valid input n between 0 and 10 inclusive

Negative input for n

How to Handle:

The constraints define valid input n between 0 and 10 inclusive so we should throw an exception or return 0 for negative inputs

Non-integer input for n

How to Handle:

Cast the input to an integer to handle floating-point or other unexpected input types

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input number n? Can n be negative or zero?
Are we counting numbers with unique digits inclusively, meaning should we include numbers from 0 up to 10^n - 1?
Are leading zeros allowed in the count (e.g., if n=2, should '01' be considered a number with unique digits)?
For n > 10, what should the return value be? Should I handle this case or is n guaranteed to be less than or equal to 10?
Could you provide a small example of the expected output for a specific value of n, such as n=2 or n=3?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start counting from zero and go up to the largest number that has the number of digits we're allowed.
For each number, look at its digits individually.
Check if any digit appears more than once within that number.
If a number has repeating digits, discard it and move on to the next number.
If a number has only unique digits, count it as a good number.
Keep counting and checking until we reach the largest possible number with the allowed number of digits.
The total count of all the 'good' numbers we found is the answer.

Code Implementation

def count_numbers_with_unique_digits_brute_force(number_of_digits):
    if number_of_digits == 0:
        return 1

    count_of_unique_digit_numbers = 0
    maximum_number = int('9' * number_of_digits)

    for number in range(maximum_number + 1):

        # Convert the number to a string to iterate through digits
        number_as_string = str(number)
        digits_seen = set()
        is_unique = True

        for digit_character in number_as_string:
            digit = int(digit_character)

            # If we've seen this digit before, it's not a unique number
            if digit in digits_seen:
                is_unique = False
                break

            digits_seen.add(digit)

        # Only increment the count if all digits are unique
        if is_unique:

            count_of_unique_digit_numbers += 1

    return count_of_unique_digit_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Realize that single-digit numbers (0-9) always have unique digits, so we know we can always start with 10.
For numbers with two digits, the first digit can be any number from 1 to 9 (9 options), and the second digit can be any digit that's not the first digit (9 options). We multiply these.
For numbers with three digits, the first digit can be any number from 1 to 9 (9 options), the second digit can be any digit that's not the first digit (9 options), and the third digit can be any digit that's not the first two digits (8 options). We multiply these.
Continue this pattern: for each additional digit, the number of options for that digit decreases by one. We keep multiplying to find the valid numbers with that many digits.
Stop when the number of digits requested is reached or when the number of available unique digits (0-9) is used up.
Sum up the number of valid numbers for each possible number of digits (1 digit, 2 digits, 3 digits, etc.) to get the final result.

Code Implementation

def count_numbers_with_unique_digits(number_of_digits):
    if number_of_digits == 0:
        return 1

    available_unique_numbers = 10
    total_unique_numbers = 10
    unique_digits_product = 9

    # Account for the first digit not being zero.
    for digit in range(2, min(number_of_digits + 1, 11)):
        unique_digits_product = unique_digits_product * (available_unique_numbers - 1)
        
        # Add the result to the total
        total_unique_numbers += unique_digits_product

        available_unique_numbers -= 1

    return total_unique_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n = 0	Return 1 since there is one number (0) with unique digits
Input n = 1	Return 10 since there are 10 single-digit numbers (0-9) with unique digits
Input n > 10	Since there are only 10 unique digits, any number with more than 10 digits must have duplicate digits, so cap n at 10.
Integer Overflow when calculating permutations	The maximum value of n is capped at 10, so integer overflow is not a concern with reasonably sized integer types.
Large value of n up to the imposed limit (n=10)	Iterative dynamic programming is more efficient than recursion as n scales up to its maximum size, avoiding stack overflow issues.
No valid solution exists other than the explicit constraints	The problem definition always ensures a solution by defining valid input n between 0 and 10 inclusive
Negative input for n	The constraints define valid input n between 0 and 10 inclusive so we should throw an exception or return 0 for negative inputs
Non-integer input for n	Cast the input to an integer to handle floating-point or other unexpected input types

Input n = 0

How to Handle:

Return 1 since there is one number (0) with unique digits

Input n = 1

How to Handle:

Return 10 since there are 10 single-digit numbers (0-9) with unique digits

Input n > 10

How to Handle:

Since there are only 10 unique digits, any number with more than 10 digits must have duplicate digits, so cap n at 10.

Integer Overflow when calculating permutations

How to Handle:

The maximum value of n is capped at 10, so integer overflow is not a concern with reasonably sized integer types.

Large value of n up to the imposed limit (n=10)

How to Handle:

Iterative dynamic programming is more efficient than recursion as n scales up to its maximum size, avoiding stack overflow issues.

No valid solution exists other than the explicit constraints

How to Handle:

The problem definition always ensures a solution by defining valid input n between 0 and 10 inclusive

Negative input for n

How to Handle:

The constraints define valid input n between 0 and 10 inclusive so we should throw an exception or return 0 for negative inputs

Non-integer input for n

How to Handle:

Cast the input to an integer to handle floating-point or other unexpected input types