Finding 3-Digit Even Numbers

Easy

Asked by:

23 views

Topics:

Arrays

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

Constraints:

3 <= digits.length <= 100
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 within the input array?
Can the input array be empty or contain null?
Are there any duplicate digits within the input array, and if so, should the resulting 3-digit even numbers also account for these duplicates?
If no 3-digit even numbers can be formed, what should the function return?
Should the output array of 3-digit even numbers be sorted in ascending order?

Brute Force Solution

Approach

The brute force approach to this problem means trying every possible combination of the given digits to form 3-digit numbers. We'll check each number to see if it meets the required conditions: being a 3-digit number and being even.

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

Imagine you have three empty slots that you need to fill with the digits you're given.
For the first slot, try putting each of the digits into it, one at a time.
For each digit you put in the first slot, try putting each of the remaining digits into the second slot.
For each combination of the first two slots, try putting each of the remaining digits into the last slot.
Now, you've created a number. Check if it is a 3-digit number (between 100 and 999).
If it's a 3-digit number, check if it's even (ends in 0, 2, 4, 6, or 8).
If it's both a 3-digit number and even, then save that number.
Repeat this process for every single combination of digits until you've tried them all.
Finally, sort all the numbers you saved from smallest to largest and remove any duplicates.

Code Implementation

def find_3_digit_even_numbers(digits):
    resulting_numbers = set()

    # Iterate through all possible permutations of digits.
    for first_index in range(len(digits)):
        for second_index in range(len(digits)):
            # Ensure that we don't reuse the same digit.
            if first_index == second_index:
                continue
            for third_index in range(len(digits)):
                if third_index == first_index or third_index == second_index:
                    continue

                number = digits[first_index] * 100 + digits[second_index] * 10 + digits[third_index]

                # Numbers must be three digits and even
                if 100 <= number <= 998:
                    if number % 2 == 0:
                        resulting_numbers.add(number)

    sorted_numbers = sorted(list(resulting_numbers))
    return sorted_numbers

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach involves trying all possible combinations of digits to form 3-digit numbers. Given an input array of size 'n', we essentially have three nested loops, each iterating through the input array's digits. The first loop selects the first digit, the second loop selects the second digit, and the third loop selects the last digit. This results in approximately n * n * n operations for generating and checking all 3-digit combinations. Therefore, the time complexity is O(n^3).

Space Complexity

O(1) – The provided brute force approach explores combinations without storing intermediate combinations explicitly except for the final result. The 'saved' numbers are the only auxiliary data structure. However, at most there are 900 3-digit numbers, and since we are filtering for even numbers only, there are even fewer possibilities. Therefore, the space required to store these numbers is constant and does not depend on the input digits. Sorting and removing duplicates from a constant-sized list takes constant space, leading to an overall space complexity of O(1).

Optimal Solution

Approach

The most efficient way to find all the possible 3-digit even numbers is to count how many times each digit appears. Then, we build the even numbers from the digits we have, making sure they're in ascending order and removing any duplicates.

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

First, count how many times each digit from 0 to 9 appears in the input.
Now, we'll build the 3-digit even numbers systematically.
The last digit of the number must be even, so we'll consider 0, 2, 4, 6, and 8 one at a time.
For each even digit, we need to find two more digits to put in front of it.
We can use any of the digits we counted earlier to form the first two digits, as long as we have enough of each digit.
The first digit cannot be zero, so we'll need to check for that.
Make sure that the first digit is less than or equal to the second, so that all the numbers can be generated in ascending order.
After creating a 3-digit even number, ensure we haven't made the same one before and add it to the output.
Finally, sort the list of numbers in ascending order before returning them.

Code Implementation

def find_3_digit_even_numbers(digits):
    digit_counts = {}
    for digit in digits:
        digit_counts[digit] = digit_counts.get(digit, 0) + 1

    results = []

    # Iterate through possible even ending digits.
    for last_digit in [0, 2, 4, 6, 8]:
        if last_digit not in digit_counts or digit_counts[last_digit] == 0:
            continue

        digit_counts[last_digit] -= 1

        # Iterate through possible first digits.
        for first_digit in range(1, 10):
            if first_digit not in digit_counts or digit_counts[first_digit] == 0:
                continue

            digit_counts[first_digit] -= 1

            # Iterate through possible second digits.
            for second_digit in range(0, 10):
                if second_digit not in digit_counts or digit_counts[second_digit] == 0:
                    continue

                # Construct the 3-digit number.
                number = first_digit * 100 + second_digit * 10 + last_digit

                # Add the number to the results list.
                results.append(number)

            digit_counts[first_digit] += 1

        digit_counts[last_digit] += 1

    # Remove duplicate numbers and then sort the results.
    unique_numbers = sorted(list(set(results)))

    return unique_numbers

Big(O) Analysis

Time Complexity

O(1) – The input size n represents the number of digits in the input array. The algorithm iterates through a fixed set of even digits (0, 2, 4, 6, 8) which is constant. For each even digit, it explores combinations for the other two digits, but the number of possible 3-digit numbers is bounded and independent of n. Therefore, the time complexity is O(1) since the operations performed are constant irrespective of the size of the input array, only depending on digits 0-9.

Space Complexity

O(1) – The algorithm uses a fixed-size array (or hash map) to count the occurrences of digits 0-9; this array has a constant size of 10, independent of the input size N (where N is the number of digits in the input). The algorithm also stores the resulting list of 3-digit numbers, but the number of such numbers is limited, as we generate them by systematically considering each possible combination and eliminating duplicates. The resulting sorted list of 3-digit even numbers has a maximum size smaller than 1000, hence the auxiliary space used is constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list, as no 3-digit even numbers can be formed.
Array with length less than 3	Return an empty list, since at least three digits are required.
Input array contains only zeros	Return a list containing only [0, 0, 0] once, representing '000' if the array has at least 3 zeros, otherwise return empty list.
No combination of digits forms a 3-digit even number	Return an empty list to indicate no valid numbers were found.
Input array contains negative numbers	Ignore negative numbers, as the problem specifies forming 3-digit numbers using digits.
Input array contains only odd numbers	Return an empty list since an even number requires at least one even digit.
The input array contains very large numbers	Ignore numbers greater than 9, as we are only looking for digits to form 3-digit numbers.
Input array contains duplicate 3-digit even numbers	The solution should correctly generate all unique 3-digit even numbers; use a set to avoid duplicates in the result.

Empty input array

How to Handle:

Return an empty list, as no 3-digit even numbers can be formed.

Array with length less than 3

How to Handle:

Return an empty list, since at least three digits are required.

Input array contains only zeros

How to Handle:

Return a list containing only [0, 0, 0] once, representing '000' if the array has at least 3 zeros, otherwise return empty list.

No combination of digits forms a 3-digit even number

How to Handle:

Return an empty list to indicate no valid numbers were found.

Input array contains negative numbers

How to Handle:

Ignore negative numbers, as the problem specifies forming 3-digit numbers using digits.

Input array contains only odd numbers

How to Handle:

Return an empty list since an even number requires at least one even digit.

The input array contains very large numbers

How to Handle:

Ignore numbers greater than 9, as we are only looking for digits to form 3-digit numbers.

Input array contains duplicate 3-digit even numbers

How to Handle:

The solution should correctly generate all unique 3-digit even numbers; use a set to avoid duplicates in the result.