Unique 3-Digit Even Numbers

Easy

Asked by:

16 views

Topics:

Arrays

You are given an array of digits called digits. Your task is to determine the number of distinct three-digit even numbers that can be formed using these digits.

Note: Each copy of a digit can only be used once per number, and there may not be leading zeros.

Example 1:

Input: digits = [1,2,3,4]

Output: 12

Explanation: The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2.

Example 2:

Input: digits = [0,2,2]

Output: 2

Explanation: The only 3-digit even numbers that can be formed are 202 and 220. Note that the digit 2 can be used twice because it appears twice in the array.

Example 3:

Input: digits = [6,6,6]

Output: 1

Explanation: Only 666 can be formed.

Example 4:

Input: digits = [1,3,5]

Output: 0

Explanation: No even 3-digit numbers can be formed.

Constraints:

3 <= digits.length <= 10
0 <= digits[i] <= 9

Try coding it in LeetCode

Unique 3-Digit Even Numbers

Easy

Asked by:

16 views

Topics:

Arrays

You are given an array of digits called digits. Your task is to determine the number of distinct three-digit even numbers that can be formed using these digits.

Note: Each copy of a digit can only be used once per number, and there may not be leading zeros.

Example 1:

Input: digits = [1,2,3,4]

Output: 12

Explanation: The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2.

Example 2:

Input: digits = [0,2,2]

Output: 2

Explanation: The only 3-digit even numbers that can be formed are 202 and 220. Note that the digit 2 can be used twice because it appears twice in the array.

Example 3:

Input: digits = [6,6,6]

Output: 1

Explanation: Only 666 can be formed.

Example 4:

Input: digits = [1,3,5]

Output: 0

Explanation: No even 3-digit numbers can be formed.

Constraints:

3 <= digits.length <= 10
0 <= digits[i] <= 9

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 values for the digits in the input array?
Can the input array contain duplicate digits, and if so, how should they be handled?
If no unique 3-digit even numbers can be formed, what should I return?
Is there a specific order in which the unique 3-digit even numbers should be returned (e.g., ascending, descending)?
Are there any size limitations on the input array length?

Brute Force Solution

Approach

The brute force approach here is like trying every possible 3-digit combination using the given digits, and then checking if the number meets the requirements: being even and having unique digits. We will generate every number possible and filter out the ones that don't fit.

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

Start by trying every possible digit for the hundreds place from the given digits.
For each hundreds digit, try every possible digit for the tens place from the given digits.
For each combination of hundreds and tens digits, try every possible digit for the ones place from the given digits.
Now you have a 3-digit number. Check if all three digits are unique (different from each other).
If the digits are not unique, discard this number and go back to trying a different combination of digits.
If the digits are unique, check if the number is even (ends in 0, 2, 4, 6, or 8).
If the number is not even, discard it and try another combination.
If the number is unique and even, save it.
Repeat this process until you have tried all possible combinations of the given digits for the hundreds, tens, and ones places.
Finally, remove any duplicate numbers from the saved numbers and sort them in ascending order.

Code Implementation

def find_unique_even_numbers(digits):
    unique_even_numbers = set()
    
    for hundreds_digit in digits:
        for tens_digit in digits:
            for ones_digit in digits:
                three_digit_number = hundreds_digit * 100 + tens_digit * 10 + ones_digit
                
                # Ensure each digit is unique

                if (hundreds_digit != tens_digit and
                    hundreds_digit != ones_digit and
                    tens_digit != ones_digit):

                    # Check if the number is even
                    if three_digit_number % 2 == 0 and three_digit_number >= 100:
                        unique_even_numbers.add(three_digit_number)

    # Convert the set to a list and sort it
    sorted_unique_even_numbers = sorted(list(unique_even_numbers))
    return sorted_unique_even_numbers

Big(O) Analysis

Time Complexity

O(n^3) – The provided brute force approach iterates through all possible 3-digit combinations formed by the input digits. We have three nested loops, each potentially iterating up to n times where n is the number of digits in the input array. Inside the loops, we perform constant time operations to check for uniqueness and evenness. Thus the dominant factor is the three nested loops, resulting in approximately n*n*n operations which simplifies to O(n^3).

Space Complexity

O(1) – The algorithm saves unique and even 3-digit numbers. The maximum number of unique 3-digit even numbers that can be formed is limited by the possible combinations and the even number constraint, regardless of the input digits. Therefore, the space required to store these numbers is constant. No other significant auxiliary space is utilized, leading to O(1) space complexity.

Optimal Solution

Approach

The best way to solve this is to carefully construct the possible 3-digit even numbers from the given digits. We want to avoid creating duplicates and make sure each number we create is actually even. We only need to construct the numbers that are even and meet all other rules.

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

First, figure out which digits are available to work with.
Since the number must be even, identify which of the given digits can be placed at the end to make the entire number even.
For each valid even digit that *can* be at the end, consider all possible digits for the first and second positions. Make sure to avoid reusing digits if the input digits are limited.
As you create each 3-digit combination, check if the number is unique (not already created).
If the number is valid, add it to a collection. If you encounter duplicates, be sure to skip them.
After you've tried all the even ending digits and made every unique combination possible, sort the collection of 3-digit even numbers in increasing order.
Present the sorted collection as your final list of valid 3-digit even numbers.

Code Implementation

def find_unique_even_numbers(digits):
    available_digits = digits
    unique_even_numbers = set()

    # Iterate through possible even digits for the last position
    for last_digit in sorted(list(set([digit for digit in available_digits if digit % 2 == 0]))):

        remaining_digits = available_digits[:]
        remaining_digits.remove(last_digit)

        # Iterate through possible digits for the first position
        for first_digit in sorted(list(set([digit for digit in remaining_digits if digit != 0]))):

            remaining_digits_second = remaining_digits[:]
            remaining_digits_second.remove(first_digit)

            # Iterate through possible digits for the second position
            for second_digit in sorted(list(set(remaining_digits_second))):

                number = first_digit * 100 + second_digit * 10 + last_digit

                # Ensure number is 3 digits, even, and unique
                if 100 <= number <= 999 and number % 2 == 0:
                    unique_even_numbers.add(number)

    # Sort the unique numbers
    sorted_unique_even_numbers = sorted(list(unique_even_numbers))

    return sorted_unique_even_numbers

Big(O) Analysis

Time Complexity

O(n^3) – Given n digits, we iterate through potential even digits to place at the end (up to n possibilities). Then, for each even digit, we iterate through possible digits for the first position (up to n possibilities) and second position (up to n possibilities). The uniqueness check implicitly involves comparing each generated number against all existing numbers (up to n, but constrained by number of valid numbers which is smaller). Thus the overall time complexity is approximately n * n * n or O(n^3).

Space Complexity

O(1) – The algorithm constructs 3-digit numbers and checks for uniqueness. The primary auxiliary space is used to store the collection of unique 3-digit even numbers. Since the possible number of unique 3-digit even numbers is bounded by a constant (maximum of 900 if all digits 0-9 were available), the space required for the collection is independent of the input array's size. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array	Return an empty list since no 3-digit numbers can be formed.
Input array size less than 3	Return an empty list since we need at least three digits to form a 3-digit number.
Input array contains only odd digits	Return an empty list because no even 3-digit number can be formed.
Input array contains no digits to form a hundred (e.g. no non-zero digits)	The algorithm should correctly skip combinations where the first digit is zero.
Input array with all the same digits (e.g., [2, 2, 2, 2])	The algorithm should generate a result (e.g. [222]) if valid and possible, otherwise return an empty list if not.
Input array containing zero and only two other distinct digits	Check for valid even combinations. e.g. [0, 1, 2], should yield [120, 210].
Duplicate valid combinations are possible, must return unique result	Store the result in a set to ensure uniqueness, and convert to list at the end.
Very large input array with a limited number of unique digits	Algorithm must still execute efficiently; using a set to ensure uniqueness is crucial