Finding 3-Digit Even Numbers

Difficulty: Easy | Acceptance: 78.70% | Paid: No Topics: Array, Hash Table, Recursion, Sorting, Enumeration

You are given an integer array digits, where each element is a digit. The array may contain duplicates. You need to return all the unique 3-digit even numbers that can be formed from the digits. A 3-digit number is an integer from 100 to 999 (inclusive). You can use the digits in the array at most once in each number.

• Examples
• Constraints
• Brute Force Enumeration
• Frequency Counting
• Backtracking

Examples

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible 3-digit even numbers that can be formed using the digits are listed.

Example 2:

Input: digits = [2,2,2,2]
Output: [222]
Explanation: The only number that can be formed is 222.

Example 3:

Input: digits = [1,2,3]
Output: [132,312]
Explanation: The numbers 132 and 312 are the only 3-digit even numbers that can be formed.

Constraints

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

Brute Force Enumeration

Intuition Since the input size is relatively small (up to 100), we can afford to check every possible combination of three digits. We iterate through all possible triplets of indices to form numbers, ensuring we use distinct indices for each digit position.

Steps

• Initialize an empty set to store unique results.
• Use three nested loops to iterate through the array indices i, j, and k.
• Ensure i, j, and k are distinct to use different digits for each place.
• Check if the digit at index k (the units place) is even.
• Form the number: digits[i] * 100 + digits[j] * 10 + digits[k].
• If the number is greater than or equal to 100 (to avoid leading zeros), add it to the set.
• Convert the set to a list, sort it, and return.

from typing import List

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        n = len(digits)
        unique_numbers = set()
        
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i != j and j != k and i != k:
                        if digits[k] % 2 == 0:
                            num = digits[i] * 100 + digits[j] * 10 + digits[k]
                            if num >= 100:
                                unique_numbers.add(num)
        
        return sorted(list(unique_numbers))

Complexity

• Time: O(n³) where n is the length of the digits array.
• Space: O(1) auxiliary space (excluding the space required for the output).
• Notes: Simple to implement but can be slow for the upper constraint limit.

Frequency Counting

Intuition Instead of generating numbers from the digits, we can iterate through all possible 3-digit even numbers (100 to 998) and check if the input digits can form that number. Since the range of 3-digit numbers is constant (450 numbers), this approach is very efficient.

Steps

• Create a frequency map (or array of size 10) to count occurrences of each digit in the input.
• Iterate through all even numbers from 100 to 998.
• For each number, count the frequency of its digits.
• Compare this frequency with the input frequency map.
• If the input has at least as many of each digit as required by the number, add the number to the result list.

from typing import List
from collections import Counter

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        count = Counter(digits)
        result = []
        
        for num in range(100, 1000, 2):
            temp_count = Counter(str(num))
            if all(count[int(d)] >= temp_count[d] for d in temp_count):
                result.append(num)
                
        return result

Complexity

• Time: O(1) because we iterate through a constant range of 450 numbers.
• Space: O(1) auxiliary space for the frequency arrays.
• Notes: This is the most optimal approach for this problem.

Backtracking

Intuition We can use recursion to explore all permutations of length 3 from the digits array. This is a standard depth-first search approach where we build the number digit by digit.

Steps

• Define a recursive function that takes the current number being built and a set of used indices.
• Base case: If the number has 3 digits, check if it is even and >= 100. If so, add to results.
• Recursive step: Iterate through all digits. If a digit is not used, add it to the current number and recurse.
• Use a set to track results to ensure uniqueness.

from typing import List

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        n = len(digits)
        res = set()
        
        def backtrack(curr, used):
            if len(curr) == 3:
                if curr[2] % 2 == 0:
                    num = curr[0] * 100 + curr[1] * 10 + curr[2]
                    if num >= 100:
                        res.add(num)
                return
            
            for i in range(n):
                if not used[i]:
                    if len(curr) == 0 and digits[i] == 0:
                        continue
                    used[i] = True
                    backtrack(curr + [digits[i]], used)
                    used[i] = False
                    
        backtrack([], [False] * n)
        return sorted(list(res))

Complexity

• Time: O(nP3) which is O(n³) in the worst case.
• Space: O(n) for the recursion stack and the used array.
• Notes: More complex to implement than brute force but demonstrates a fundamental algorithmic pattern.