2094: Finding 3-Digit Even Numbers

Difficulty: Easy

Topics: Arrays, Combinatorics, Sorting

Companies: Google, Microsoft, Adobe

Optimization Insight: Generate numbers from 100 to 998 (step 2) and check digit availability for O(1) space complexity.

Problem Statement

Given an array of digits (0-9), return all unique 3-digit even numbers that can be formed using these digits without leading zeros.

Example 1

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]

Example 2

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]

Problem Link: View on LeetCode ↗

Approach 1: Brute-force Check (Optimal)

Iterate through all possible 3-digit even numbers and verify digit availability.

Algorithm Steps

Generate numbers from 100 to 998 with step 2
For each number, check if all digits exist in input
Use frequency count to handle duplicates

Complexity Analysis

Time Complexity	Space Complexity
O(450 * n)	O(n)

Optimal Solution

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> res;
        int count[10] = {0};
        for(int d : digits) count[d]++;
        
        for(int num = 100; num < 999; num += 2) {
            int temp[10] = {0};
            int n = num;
            temp[n%10]++; n /= 10;
            temp[n%10]++; n /= 10;
            temp[n%10]++;
            
            if(temp[0] > count[0]) continue;
            bool valid = true;
            for(int i=1; i<10; i++) {
                if(temp[i] > count[i]) {
                    valid = false;
                    break;
                }
            }
            if(valid) res.push_back(num);
        }
        return res;
    }
};

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        List<Integer> res = new ArrayList<>();
        int[] count = new int[10];
        for(int d : digits) count[d]++;
        
        for(int num = 100; num < 999; num += 2) {
            int[] temp = new int[10];
            int n = num;
            temp[n%10]++; n /= 10;
            temp[n%10]++; n /= 10;
            temp[n%10]++;
            
            if(temp[0] > count[0]) continue;
            boolean valid = true;
            for(int i=1; i<10; i++) {
                if(temp[i] > count[i]) {
                    valid = false;
                    break;
                }
            }
            if(valid) res.add(num);
        }
        return res.stream().mapToInt(i->i).toArray();
    }
}

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        freq = Counter(digits)
        res = []
        
        for num in range(100, 999, 2):
            temp = defaultdict(int)
            n = num
            temp[n%10] += 1
            n //= 10
            temp[n%10] += 1
            n //= 10
            temp[n%10] += 1
            
            if temp[0] > freq.get(0, 0):
                continue
                
            valid = True
            for d in temp:
                if d == 0:
                    continue
                if temp[d] > freq.get(d, 0):
                    valid = False
                    break
                    
            if valid:
                res.append(num)
                
        return res

Efficiency Note: This approach checks only 450 numbers (100-998 even) making it O(1) in practice for large digit arrays.

Approach 2: Permutation Generation

Generate all valid 3-digit combinations and filter results.

Algorithm Steps

Generate all 3-digit permutations with replacement
Filter numbers with leading zeros and odd numbers
Use set to eliminate duplicates

Complexity Analysis

Time Complexity	Space Complexity
O(n³)	O(n³)

Combinatorial Solution

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        unordered_set<int> res;
        int n = digits.size();
        
        for(int i = 0; i < n; i++) {
            if(digits[i] == 0) continue;
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    if(i == j || j == k || i == k) continue;
                    int num = digits[i]*100 + digits[j]*10 + digits[k];
                    if(num % 2 == 0) res.insert(num);
                }
            }
        }
        
        vector<int> result(res.begin(), res.end());
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> res = new HashSet<>();
        int n = digits.length;
        
        for(int i = 0; i < n; i++) {
            if(digits[i] == 0) continue;
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    if(i == j || j == k || i == k) continue;
                    int num = digits[i]*100 + digits[j]*10 + digits[k];
                    if(num % 2 == 0) res.add(num);
                }
            }
        }
        
        return res.stream().sorted().mapToInt(i->i).toArray();
    }
}

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

Implementation Note: While intuitive, this approach becomes inefficient for large input sizes (n=100 → 1,000,000 iterations).

Approach Comparison

Approach	Time	Space	Best Use Case
Brute-force Check	O(450n)	O(n)	Large input sizes
Permutation Generation	O(n³)	O(n³)	Small input sizes

Performance Note: The permutation approach becomes impractical for n > 20 (4000+ operations vs 450*20=9000 for brute-force).

Edge Cases and Testing

1. All Zeros

Input: [0,0,0] → Output: []

2. Single Non-zero Digit

Input: [2,2,2] → Output: [222]

3. No Even Numbers Possible

Input: [1,3,5] → Output: []

Critical Check: Always verify the last digit is even and first digit is non-zero in all generated numbers.

Frequently Asked Questions

1. Why use frequency counting in optimal approach?

To handle duplicate digits efficiently and verify digit availability in O(1) time per number.

2. How to handle duplicate digits in permutation approach?

Using a Set data structure automatically eliminates duplicate combinations.

3. Why start from 100 and increment by 2?

Ensures we only check even numbers and skip invalid numbers with leading zeros.

4. Can we optimize permutation generation?

Yes, by pre-filtering even digits for last position and non-zero digits for first position.

5. How does the optimal approach handle duplicates?

By checking frequency counts rather than tracking indices, allowing natural handling of duplicates.

6. What's the maximum possible numbers to check?

450 numbers (from 100 to 998 with step 2), making the optimal approach very efficient.

7. Why sort the result at the end?

To meet problem requirements of returning numbers in sorted order.

8. How to handle input with less than 3 digits?

Problem constraints guarantee at least 3 digits, so no need to handle this case.

9. What if input contains negative numbers?

Problem constraints specify digits are 0-9, so no negative values to handle.

10. Real-world applications of this problem?

Combination locks, password generation, and inventory code validation systems.

Final Observation: This problem demonstrates the importance of choosing the right approach based on input constraints. While combinatorial solutions seem natural, mathematical insights often provide more efficient answers.