Jobs

Interviews

Discussions

Count Numbers With Unique Digits II

Easy

Asked by:

15 views

Topics:

Dynamic ProgrammingRecursionArrays

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having all digits unique.

Example 1:

Input: left = 1, right = 20
Output: 19
Explanation: All numbers from 1 to 20 have unique digits.

Example 2:

Input: left = 100, right = 110
Output: 10
Explanation: The numbers in the range [100, 110] with unique digits are: 102, 103, 104, 105, 106, 107, 108, 109, 110 (skipping 100 and 101 as they have duplicate digits).
The count is 10.

Constraints:

1 <= left <= right <= 10⁸

Try coding it in LeetCode

Count Numbers With Unique Digits II

Easy

Asked by:

15 views

Topics:

Dynamic ProgrammingRecursionArrays

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having all digits unique.

Example 1:

Input: left = 1, right = 20
Output: 19
Explanation: All numbers from 1 to 20 have unique digits.

Example 2:

Input: left = 100, right = 110
Output: 10
Explanation: The numbers in the range [100, 110] with unique digits are: 102, 103, 104, 105, 106, 107, 108, 109, 110 (skipping 100 and 101 as they have duplicate digits).
The count is 10.

Constraints:

1 <= left <= right <= 10⁸

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:

Could you please clarify the acceptable range for the input number 'n'? Is there a maximum value for 'n' that I should be aware of?
Should I consider 0 as a number with unique digits? For example, is n=0 a valid input, and if so, what should the output be?
Are we looking for numbers with strictly unique digits, or is there some threshold for the number of repetitions allowed?
Is the expectation that the output be a total count of the numbers, or a list of those numbers themselves?
If there are no numbers with unique digits within the specified range, what should the function return? Should it return 0, -1, or throw an exception?

Brute Force Solution

Approach

To find the numbers with unique digits within a given range using a brute force approach, we essentially check every single number within that range. For each number, we then verify if all of its digits are different from each other.

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

Start with the beginning number of the range.
Check if this number has all unique digits. Do this by looking at each digit and comparing it to all the other digits in the number. If you find any duplicates, then this number does not have unique digits.
If the number has all unique digits, add it to a count of the numbers with unique digits.
Move to the next number in the range.
Repeat the checking and counting process until you have checked every number up to the end of the range.
The final count will be the total number of numbers with unique digits in that range.

Code Implementation

def count_numbers_with_unique_digits_brute_force(start_range, end_range):
    count_unique_digits = 0

    for number in range(start_range, end_range + 1):
        number_string = str(number)
        digits_seen = set()
        is_unique = True

        # Check each digit of current number
        for digit_character in number_string:
            digit = int(digit_character)

            # If digit is already seen, not unique
            if digit in digits_seen:
                is_unique = False

                break

            digits_seen.add(digit)

        # Increment count if the digits were all unique
        if is_unique:
            count_unique_digits += 1

    return count_unique_digits

Big(O) Analysis

Time Complexity

O((b-a) * log10(b)) – Let n be the range of numbers between a and b. We iterate through each number in this range (b-a times). For each number, we determine if its digits are unique. In the worst case, we need to examine each digit of the number to check for uniqueness. The number of digits in a number is roughly log10(number). Therefore, for each number, we perform log10(b) operations in the worst case. Overall, the time complexity is O((b-a) * log10(b)).

Space Complexity

O(1) – The provided brute force approach checks each number within the input range for unique digits. For each number, it compares digits to each other to detect duplicates. This digit comparison process does not create any auxiliary data structures, such as lists or hash maps, to store intermediate results or visited digits. The algorithm uses a fixed number of variables to store the current number being checked and potentially a few loop counters. Therefore, the space complexity is constant and independent of the size of the range (N).

Optimal Solution

Approach

The problem is about counting numbers with unique digits within a specified range. The efficient approach avoids generating and checking every single number by using combinatorics and dynamic programming to calculate the count directly.

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

Understand that single-digit numbers always have unique digits.
Calculate the count of numbers with unique digits for each possible length, from 1 up to the maximum length specified by the range.
For a number of length 'n', the first digit has 9 choices (1-9, excluding 0), and the second digit has 9 choices (0-9, excluding the first digit), and so on.
Use this pattern of decreasing choices for each digit to calculate the number of valid numbers for each length. For example, for length 2, it would be 9 * 9, and for length 3 it would be 9 * 9 * 8.
Take the lower and upper bounds of the range into account.
Sum up the counts for all valid lengths that fall within the range. However, also handle the cases where the bounds of the range constrain the lengths by trimming off some numbers that do not fall between the high and low range.
Return the final count, which represents the number of numbers with unique digits in the specified range.

Code Implementation

def count_numbers_with_unique_digits_ii(low_range, high_range):
    if low_range > high_range:
        return 0

    count = 0

    # Single digit numbers always have unique digits
    if low_range <= 0 <= high_range:
        count += 1

    for number_length in range(1, 11):
        if number_length == 1:
            unique_digit_count = 9
        else:
            unique_digit_count = 9
            available_digits = 9

            # Calculate the count for the current length
            for _ in range(number_length - 1):
                unique_digit_count *= available_digits
                available_digits -= 1

        lower_bound = 10 ** (number_length - 1)
        upper_bound = (10 ** number_length) - 1

        # Numbers of this length are within the range
        if lower_bound >= low_range and upper_bound <= high_range:
            count += unique_digit_count

        # Adjust for low_range bound
        elif lower_bound < low_range <= upper_bound:
            count += count_valid_numbers_in_range(low_range, upper_bound, number_length)

        # Adjust for high_range bound
        elif lower_bound <= high_range < upper_bound:
            count += count_valid_numbers_in_range(lower_bound, high_range, number_length)

        # The range lies entirely within this length
        elif low_range < lower_bound and high_range > upper_bound:
           count += unique_digit_count

    return count

def count_valid_numbers_in_range(lower_bound, upper_bound, number_length):
    count = 0
    for number in range(lower_bound, upper_bound + 1):
        if has_unique_digits(number):
            count += 1

    return count

def has_unique_digits(number):
    digits = set()
    for digit in str(number):
        if digit in digits:
            return False
        digits.add(digit)

    return True

Big(O) Analysis

Time Complexity

O(log(max(low, high))) – The algorithm iterates up to the number of digits in the higher bound (high) of the range. The number of digits in a number is proportional to the logarithm (base 10) of that number. Therefore, the loop runs a maximum of log(high) times. Because the calculations inside the loop take constant time, the overall time complexity is determined by the number of loop iterations, which is approximately log(high). We take max(low, high) to account for the lower bound being larger than the upper bound, which is an unlikely but possible edge case.

Space Complexity

O(1) – The algorithm primarily uses a few integer variables for loop counters, the current number being built, and the count of valid numbers. The problem does not explicitly mention creating any auxiliary data structures like arrays, lists, or hash maps whose size depends on the input range. Therefore, the auxiliary space used is constant, independent of the size of the input range (lower and upper bounds). This constant space usage simplifies to O(1).

Edge Cases

Case	How to Handle
n = 0	Return 1 since a number with 0 digits (empty number) is considered to have unique digits.
n = 1	Return 10 because the unique numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
n > 10	Return the same result as n = 10 because a number with more than 10 digits cannot have all unique digits.
Integer overflow for large n during calculation	Ensure the data type used for intermediate calculations and final result is large enough (e.g., long) to prevent integer overflow.
All possible digits are used up at some i < n	The loop should terminate when the number of unique digits reaches the maximum possible.
Negative input for n	Throw an IllegalArgumentException or return 0 since negative input is not a valid number of digits.
Edge case where n is close to overflow range	Handle intermediate results and ensure that they do not overflow, likely requiring `long` rather than `int`.
Empty digit sequences	Count the empty sequence as the case when n=0, thus returning 1.

n = 0

How to Handle:

Return 1 since a number with 0 digits (empty number) is considered to have unique digits.

n = 1

How to Handle:

Return 10 because the unique numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

n > 10

How to Handle:

Return the same result as n = 10 because a number with more than 10 digits cannot have all unique digits.

Integer overflow for large n during calculation

How to Handle:

Ensure the data type used for intermediate calculations and final result is large enough (e.g., long) to prevent integer overflow.

All possible digits are used up at some i < n

How to Handle:

The loop should terminate when the number of unique digits reaches the maximum possible.

Negative input for n

How to Handle:

Throw an IllegalArgumentException or return 0 since negative input is not a valid number of digits.

Edge case where n is close to overflow range

How to Handle:

Handle intermediate results and ensure that they do not overflow, likely requiring `long` rather than `int`.

Empty digit sequences

How to Handle:

Count the empty sequence as the case when n=0, thus returning 1.

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:

Could you please clarify the acceptable range for the input number 'n'? Is there a maximum value for 'n' that I should be aware of?
Should I consider 0 as a number with unique digits? For example, is n=0 a valid input, and if so, what should the output be?
Are we looking for numbers with strictly unique digits, or is there some threshold for the number of repetitions allowed?
Is the expectation that the output be a total count of the numbers, or a list of those numbers themselves?
If there are no numbers with unique digits within the specified range, what should the function return? Should it return 0, -1, or throw an exception?

Brute Force Solution

Approach

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

Start with the beginning number of the range.
Check if this number has all unique digits. Do this by looking at each digit and comparing it to all the other digits in the number. If you find any duplicates, then this number does not have unique digits.
If the number has all unique digits, add it to a count of the numbers with unique digits.
Move to the next number in the range.
Repeat the checking and counting process until you have checked every number up to the end of the range.
The final count will be the total number of numbers with unique digits in that range.

Code Implementation

def count_numbers_with_unique_digits_brute_force(start_range, end_range):
    count_unique_digits = 0

    for number in range(start_range, end_range + 1):
        number_string = str(number)
        digits_seen = set()
        is_unique = True

        # Check each digit of current number
        for digit_character in number_string:
            digit = int(digit_character)

            # If digit is already seen, not unique
            if digit in digits_seen:
                is_unique = False

                break

            digits_seen.add(digit)

        # Increment count if the digits were all unique
        if is_unique:
            count_unique_digits += 1

    return count_unique_digits

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Understand that single-digit numbers always have unique digits.
Calculate the count of numbers with unique digits for each possible length, from 1 up to the maximum length specified by the range.
For a number of length 'n', the first digit has 9 choices (1-9, excluding 0), and the second digit has 9 choices (0-9, excluding the first digit), and so on.
Use this pattern of decreasing choices for each digit to calculate the number of valid numbers for each length. For example, for length 2, it would be 9 * 9, and for length 3 it would be 9 * 9 * 8.
Take the lower and upper bounds of the range into account.
Sum up the counts for all valid lengths that fall within the range. However, also handle the cases where the bounds of the range constrain the lengths by trimming off some numbers that do not fall between the high and low range.
Return the final count, which represents the number of numbers with unique digits in the specified range.

Code Implementation

def count_numbers_with_unique_digits_ii(low_range, high_range):
    if low_range > high_range:
        return 0

    count = 0

    # Single digit numbers always have unique digits
    if low_range <= 0 <= high_range:
        count += 1

    for number_length in range(1, 11):
        if number_length == 1:
            unique_digit_count = 9
        else:
            unique_digit_count = 9
            available_digits = 9

            # Calculate the count for the current length
            for _ in range(number_length - 1):
                unique_digit_count *= available_digits
                available_digits -= 1

        lower_bound = 10 ** (number_length - 1)
        upper_bound = (10 ** number_length) - 1

        # Numbers of this length are within the range
        if lower_bound >= low_range and upper_bound <= high_range:
            count += unique_digit_count

        # Adjust for low_range bound
        elif lower_bound < low_range <= upper_bound:
            count += count_valid_numbers_in_range(low_range, upper_bound, number_length)

        # Adjust for high_range bound
        elif lower_bound <= high_range < upper_bound:
            count += count_valid_numbers_in_range(lower_bound, high_range, number_length)

        # The range lies entirely within this length
        elif low_range < lower_bound and high_range > upper_bound:
           count += unique_digit_count

    return count

def count_valid_numbers_in_range(lower_bound, upper_bound, number_length):
    count = 0
    for number in range(lower_bound, upper_bound + 1):
        if has_unique_digits(number):
            count += 1

    return count

def has_unique_digits(number):
    digits = set()
    for digit in str(number):
        if digit in digits:
            return False
        digits.add(digit)

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 1 since a number with 0 digits (empty number) is considered to have unique digits.
n = 1	Return 10 because the unique numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
n > 10	Return the same result as n = 10 because a number with more than 10 digits cannot have all unique digits.
Integer overflow for large n during calculation	Ensure the data type used for intermediate calculations and final result is large enough (e.g., long) to prevent integer overflow.
All possible digits are used up at some i < n	The loop should terminate when the number of unique digits reaches the maximum possible.
Negative input for n	Throw an IllegalArgumentException or return 0 since negative input is not a valid number of digits.
Edge case where n is close to overflow range	Handle intermediate results and ensure that they do not overflow, likely requiring `long` rather than `int`.
Empty digit sequences	Count the empty sequence as the case when n=0, thus returning 1.

n = 0

How to Handle:

Return 1 since a number with 0 digits (empty number) is considered to have unique digits.

n = 1

How to Handle:

Return 10 because the unique numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

n > 10

How to Handle:

Return the same result as n = 10 because a number with more than 10 digits cannot have all unique digits.

Integer overflow for large n during calculation

How to Handle:

Ensure the data type used for intermediate calculations and final result is large enough (e.g., long) to prevent integer overflow.

All possible digits are used up at some i < n

How to Handle:

The loop should terminate when the number of unique digits reaches the maximum possible.

Negative input for n

How to Handle:

Throw an IllegalArgumentException or return 0 since negative input is not a valid number of digits.

Edge case where n is close to overflow range

How to Handle:

Handle intermediate results and ensure that they do not overflow, likely requiring `long` rather than `int`.

Empty digit sequences

How to Handle:

Count the empty sequence as the case when n=0, thus returning 1.