# Finding 3-Digit Even Numbers
**Difficulty:** EASY
[External](https://leetcode.com/problems/finding-3-digit-even-numbers)
Canonical: https://scaleengineer.com/dsa/problems/finding-3-digit-even-numbers
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute-Force with Nested Loops
This approach generates all possible 3-digit numbers by picking three distinct digits from the input array. It uses three nested loops to iterate through all combinations of three indices, forms a number, and checks if it's a valid 3-digit even number without a leading zero. A `HashSet` is used to store the unique numbers, which are then sorted before being returned.
**Time:** O(n^3 + K log K), where `n` is the length of the `digits` array and `K` is the number of unique valid numbers found. The three nested loops result in O(n^3) complexity. Sorting the final result adds O(K log K). Given `n <= 100`, this is feasible but slow. · **Space:** O(K), where K is the number of unique valid numbers. Since K is at most 450 (the number of 3-digit even numbers), the space complexity is effectively O(1), excluding the storage for the output array.
**Pros:** Conceptually simple and straightforward to implement.; Correctly solves the problem for the given constraints.
**Cons:** Highly inefficient with a time complexity of O(n^3), which can be very slow if the input array size `n` were larger.; Performs many redundant checks, especially when the input array contains duplicate digits.
### Explanation
The core idea is to exhaustively explore all permutations of size 3 from the given `digits` array. We can achieve this using three nested loops, where each loop iterates through the `digits` array to pick a digit for the hundreds, tens, and units place, respectively. To ensure we use three *different* elements from the array, we check that the indices `i`, `j`, and `k` are all distinct. For each valid combination of indices, we construct the number and verify two conditions: the first digit (from `digits[i]`) is not zero, and the last digit (from `digits[k]`) is even. Valid numbers are added to a `HashSet` to automatically handle uniqueness. Finally, the contents of the set are transferred to an array and sorted.

```java
import java.util.*;

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> resultSet = new HashSet<>();
        int n = digits.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i == j || j == k || i == k) {
                        continue;
                    }
                    if (digits[i] != 0 && digits[k] % 2 == 0) {
                        int num = digits[i] * 100 + digits[j] * 10 + digits[k];
                        resultSet.add(num);
                    }
                }
            }
        }
        int[] result = new int[resultSet.size()];
        int index = 0;
        for (int num : resultSet) {
            result[index++] = num;
        }
        Arrays.sort(result);
        return result;
    }
}
```
### Algorithm
1. Initialize a `Set<Integer>` to store unique valid numbers, preventing duplicates.
2. Get the length of the input `digits` array, `n`.
3. Use three nested loops with indices `i`, `j`, and `k` to iterate from `0` to `n-1`.
4. Inside the innermost loop, check if the indices are distinct: `i != j`, `j != k`, and `i != k`.
5. If the indices are distinct, retrieve the digits: `d1 = digits[i]`, `d2 = digits[j]`, `d3 = digits[k]`.
6. Check if the formed number meets the problem's requirements:
   - No leading zero: `d1 != 0`.
   - Is an even number: `d3 % 2 == 0`.
7. If both conditions are met, form the number `num = d1 * 100 + d2 * 10 + d3` and add it to the `Set`.
8. After the loops complete, convert the `Set` into an array.
9. Sort the resulting array in ascending order.
10. Return the sorted array.

## Frequency Count and Number Generation
This approach improves upon brute-force by first counting the frequency of each digit. Instead of iterating through the input array, it iterates through all possible digit combinations for a 3-digit even number (e.g., hundreds digit from 1-9, tens from 0-9, units from 0,2,4,6,8). For each combination, it checks if there are enough digits available in the frequency map to form the number.
**Time:** O(n). The initial frequency counting takes O(n) time. The subsequent nested loops run a fixed number of times (450), which is a constant. Therefore, the overall time complexity is dominated by the initial scan of the input array. · **Space:** O(1). The frequency map has a constant size of 10. The result list stores at most 450 numbers, which is also constant. Thus, the space is O(1) excluding the output array.
**Pros:** Very efficient with a time complexity of O(n), as the number of combinations to check is constant (9 * 10 * 5 = 450).; Avoids using a Set and a final sort, as numbers are generated in ascending order.
**Cons:** The logic of decrementing and then restoring counts (backtracking) can be slightly more complex to reason about compared to the most optimal approach.
### Explanation
Instead of iterating through permutations of the input array indices, we can iterate through the possibilities for the final numbers themselves. We start by creating a frequency map of the input digits, which takes O(n) time. Then, we construct all possible 3-digit even numbers. A 3-digit number has a hundreds digit from 1-9, a tens digit from 0-9, and an even units digit from {0, 2, 4, 6, 8}. We can use three nested loops to iterate through these possibilities. For each potential number, we check if we have the required digits by temporarily decrementing their counts in our frequency map. If we can form the number (i.e., the counts don't go below zero), we add it to our result list. We must then restore the counts (backtrack) so they are available for the next potential number. This method avoids the O(n^3) complexity and generates the numbers in sorted order naturally.

```java
import java.util.*;

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        int[] counts = new int[10];
        for (int digit : digits) {
            counts[digit]++;
        }

        List<Integer> resultList = new ArrayList<>();
        for (int i = 1; i <= 9; i++) { // Hundreds digit
            for (int j = 0; j <= 9; j++) { // Tens digit
                for (int k = 0; k <= 8; k += 2) { // Units digit (must be even)
                    counts[i]--;
                    counts[j]--;
                    counts[k]--;

                    if (counts[i] >= 0 && counts[j] >= 0 && counts[k] >= 0) {
                        resultList.add(i * 100 + j * 10 + k);
                    }

                    // Backtrack: restore the counts
                    counts[i]++;
                    counts[j]++;
                    counts[k]++;
                }
            }
        }

        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}
```
### Algorithm
1. Create a frequency array `counts` of size 10 to store the count of each digit (0-9) from the input `digits` array.
2. Initialize an empty list, `resultList`, to store the valid numbers.
3. Use three nested loops to generate numbers:
   - The outer loop for the hundreds digit `i` runs from `1` to `9` (to avoid leading zeros).
   - The middle loop for the tens digit `j` runs from `0` to `9`.
   - The inner loop for the units digit `k` runs from `0` to `8` with a step of 2 (to ensure the number is even).
4. For each combination `(i, j, k)`, check if it can be formed from the available digits:
   - Temporarily decrement the counts for `i`, `j`, and `k` in the `counts` array.
   - If all counts (`counts[i]`, `counts[j]`, `counts[k]`) remain non-negative, the number is valid.
   - If valid, construct the number `num = i * 100 + j * 10 + k` and add it to `resultList`.
   - **Crucially**, restore the counts by incrementing `counts[i]`, `counts[j]`, and `counts[k]` to backtrack for the next iteration.
5. The `resultList` will be naturally sorted because the loops generate numbers in increasing order.
6. Convert the `resultList` to an array and return it.

## Frequency Count and Checking All Even Numbers
This is the most efficient approach. It reverses the logic: instead of building numbers from the given digits, it iterates through all possible valid outcomes (all 3-digit even numbers from 100 to 998) and checks if each one can be constructed from the available digits. This is done by comparing the frequency of digits required for the target number with the frequency of digits available from the input.
**Time:** O(n). The initial scan to build the frequency map takes O(n). The main loop runs a constant number of times (450 iterations), and the work inside is constant time. The overall complexity is O(n). · **Space:** O(1). We use a few constant-size frequency arrays. The result list stores at most 450 numbers, which is a constant. Therefore, the space complexity is constant, excluding the output array.
**Pros:** The most efficient and cleanest solution.; Time complexity is linear, O(n), and independent of `n` after the initial count.; The logic is straightforward: iterate through all candidates and check feasibility.; Naturally produces a sorted result, avoiding an explicit sort operation.
**Cons:** This approach is optimal for the given constraints, so it has no significant cons.
### Explanation
The most direct way to solve this problem is to realize that the set of possible answers is small and fixed. All possible results must be 3-digit even numbers, which range from 100 to 998. We can simply iterate through every even number in this range and, for each one, check if we have the necessary digits in our input array.

First, we pre-process the input `digits` into a frequency map, `sourceCounts`, in O(n) time. Then, we loop from `num = 100` to `998` in steps of 2. For each `num`, we determine its digit composition (e.g., 242 needs two '2's and one '4'). We can create a temporary frequency map, `targetCounts`, for `num`. We then verify if `sourceCounts` can satisfy `targetCounts` by checking if `sourceCounts[d] >= targetCounts[d]` for every digit `d`. If it can, we add `num` to our result list. Because we iterate through the numbers in ascending order, the final list is already sorted, eliminating the need for a separate sorting step.

```java
import java.util.*;

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        int[] sourceCounts = new int[10];
        for (int digit : digits) {
            sourceCounts[digit]++;
        }

        List<Integer> resultList = new ArrayList<>();
        for (int num = 100; num <= 998; num += 2) {
            int[] targetCounts = new int[10];
            targetCounts[num / 100]++;
            targetCounts[(num / 10) % 10]++;
            targetCounts[num % 10]++;

            boolean possible = true;
            for (int i = 0; i < 10; i++) {
                if (sourceCounts[i] < targetCounts[i]) {
                    possible = false;
                    break;
                }
            }

            if (possible) {
                resultList.add(num);
            }
        }

        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}
```
### Algorithm
1. Create a frequency array `sourceCounts` of size 10 and populate it by iterating through the input `digits` array.
2. Initialize an empty `List<Integer>` to store the results.
3. Iterate through all 3-digit even numbers, i.e., loop `num` from `100` to `998` with a step of 2.
4. For each `num`:
   a. Deconstruct `num` into its three digits: `d1` (hundreds), `d2` (tens), and `d3` (units).
   b. Create a frequency map `targetCounts` for the digits of `num`.
   c. Compare the `targetCounts` with the `sourceCounts`. Check if `sourceCounts[d] >= targetCounts[d]` for all digits `d` from 0 to 9.
5. If the check passes, it means `num` can be formed from the given digits, so add `num` to the result list.
6. Since the loop iterates through numbers in increasing order, the result list is already sorted.
7. Convert the list to an array and return it.

# Solutions
### Java

```java
class Solution {
public
  int[] findEvenNumbers(int[] digits) {
    int[] counter = count(digits);
    List<Integer> ans = new ArrayList<>();
    for (int i = 100; i < 1000; i += 2) {
      int[] t = new int[3];
      for (int j = 0, k = i; k > 0; ++j) {
        t[j] = k % 10;
        k /= 10;
      }
      int[] cnt = count(t);
      if (check(counter, cnt)) {
        ans.add(i);
      }
    }
    return ans.stream().mapToInt(Integer : : valueOf).toArray();
  }
private
  boolean check(int[] cnt1, int[] cnt2) {
    for (int i = 0; i < 10; ++i) {
      if (cnt1[i] < cnt2[i]) {
        return false;
      }
    }
    return true;
  }
private
  int[] count(int[] nums) {
    int[] counter = new int[10];
    for (int num : nums) {
      ++counter[num];
    }
    return counter;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} digits * @return {number[]} */ var findEvenNumbers =
  function (digits) {
    const cnt = Array(10).fill(0);
    for (const x of digits) {
      ++cnt[x];
    }
    const ans = [];
    for (let x = 100; x < 1000; x += 2) {
      const cnt1 = Array(10).fill(0);
      for (let y = x; y; y = Math.floor(y / 10)) {
        ++cnt1[y % 10];
      }
      let ok = true;
      for (let i = 0; i < 10 && ok; ++i) {
        ok = cnt[i] >= cnt1[i];
      }
      if (ok) {
        ans.push(x);
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> findEvenNumbers(vector<int> &digits) {
    vector<int> counter = count(digits);
    vector<int> ans;
    for (int i = 100; i < 1000; i += 2) {
      vector<int> t(3);
      for (int j = 0, k = i; k > 0; ++j) {
        t[j] = k % 10;
        k /= 10;
      }
      vector<int> cnt = count(t);
      if (check(counter, cnt))
        ans.push_back(i);
    }
    return ans;
  }
  vector<int> count(vector<int> &nums) {
    vector<int> counter(10);
    for (int num : nums)
      ++counter[num];
    return counter;
  }
  bool check(vector<int> &cnt1, vector<int> &cnt2) {
    for (int i = 0; i < 10; ++i)
      if (cnt1[i] < cnt2[i])
        return false;
    return true;
  }
};

```

### Python

```python
class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]: ans = [] counter = Counter(digits) for i in range(100, 1000, 2): t = [] k = i while k: t . append(k % 10) k //= 10 cnt = Counter(t) if all([counter[i] >= cnt[i] for i in range(10)]): ans . append(i) return ans

```