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

# Approaches
## Brute-Force with Nested Loops
This approach directly simulates the process of forming 3-digit numbers by picking three distinct digits from the input array. We use three nested loops to explore every possible way to choose three digits for the hundreds, tens, and units places. For each valid combination that forms a 3-digit even number, we add it to a set to ensure uniqueness.
**Time:** O(n^3 + U log U), where n is the length of the `digits` array and U is the number of unique numbers found. The three nested loops result in `O(n^3)` complexity. Sorting the final result takes an additional `O(U log U)`. Given `n <= 10`, this is efficient enough. · **Space:** O(U), where U is the number of unique valid 3-digit even numbers. The space is primarily used for the `HashSet` to store the results. The maximum number of such numbers is 450, so the space complexity is effectively constant.
**Pros:** The logic is straightforward and easy to understand as it directly models the problem statement.; It's relatively simple to implement without requiring complex data structures or algorithms.
**Cons:** The `O(n^3)` time complexity is inefficient for larger input sizes, though it's acceptable for the given constraints (`n <= 10`).; It generates many combinations that are immediately discarded (e.g., those with leading zeros or non-distinct indices), leading to wasted computations.
### Explanation
The core idea is to exhaustively check every permutation of three digits from the input array. We can implement this using three nested loops that iterate from `0` to `n-1`, where `n` is the length of the `digits` array. The loop variables `i`, `j`, and `k` represent the indices of the digits we pick.

To ensure that we use each digit at most once per number, we must verify that the indices `i`, `j`, and `k` are all different from each other. Once we have three distinct digits, `digits[i]`, `digits[j]`, and `digits[k]`, we check if they can form a valid 3-digit even number. The conditions are:
1.  `digits[i]` (the hundreds digit) cannot be zero.
2.  `digits[k]` (the units digit) must be an even number.

If these conditions are satisfied, we construct the number and add it to a `HashSet`. The set automatically handles duplicates that might arise from different permutations of identical digits (e.g., if `digits = [2, 1, 2]`, both `(2,1,2)` and `(2,1,2)` using different '2's would form 212, but the set stores it only once). Finally, the contents of the set are converted into a sorted integer array.

```java
import java.util.*;

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> uniqueNumbers = 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++) {
                    // Ensure we are using digits from three different positions
                    if (i == j || j == k || i == k) {
                        continue;
                    }

                    int d1 = digits[i]; // Hundreds digit
                    int d2 = digits[j]; // Tens digit
                    int d3 = digits[k]; // Units digit

                    // Check for leading zero
                    if (d1 == 0) {
                        continue;
                    }

                    // Check if the number is even
                    if (d3 % 2 != 0) {
                        continue;
                    }

                    int number = d1 * 100 + d2 * 10 + d3;
                    uniqueNumbers.add(number);
                }
            }
        }

        // Convert set to sorted array
        int[] result = new int[uniqueNumbers.size()];
        int index = 0;
        for (int num : uniqueNumbers) {
            result[index++] = num;
        }
        Arrays.sort(result);
        return result;
    }
}
```
### Algorithm
- Initialize a `HashSet<Integer>` to store the unique numbers found.
- Use three nested loops, with indices `i`, `j`, and `k`, to iterate through all combinations of three positions in the `digits` array.
- Inside the innermost loop, check if the indices `i`, `j`, and `k` are all distinct. If not, continue to the next iteration.
- If the indices are distinct, retrieve the digits: `d1 = digits[i]`, `d2 = digits[j]`, `d3 = digits[k]`.
- Validate the formed number:
  - The first digit `d1` must not be 0 (to avoid numbers less than 100).
  - The last digit `d3` must be even (`d3 % 2 == 0`).
- If both conditions are met, form the number `num = d1 * 100 + d2 * 10 + d3` and add it to the `HashSet`.
- After the loops complete, convert the set to an array and sort it to get the final result.

## Fixed Range Iteration with Frequency Counting
A more efficient approach is to change the perspective: instead of generating numbers from the given digits, we can iterate through all possible 3-digit even numbers and check if each one can be constructed using the available digits. The range of 3-digit even numbers is fixed (100, 102, ..., 998), making the number of checks constant.
**Time:** O(n). The initial scan to build the frequency map takes `O(n)` time. The main loop runs a constant number of times (450 iterations for even numbers from 100 to 998). Inside the loop, operations are constant time. Thus, the overall complexity is dominated by the initial scan. · **Space:** O(1). The space used includes the frequency map (`digitCounts`) of size 10 and the result list. The maximum size of the result list is fixed (450 possible 3-digit even numbers), making the space requirement constant.
**Pros:** Extremely efficient, with a time complexity that is almost constant, only depending linearly on `n` for the initial count.; The number of main operations is fixed regardless of the input `digits` array's size and values.; Avoids complex permutation/combination logic and automatically handles uniqueness.; The resulting list of numbers is generated in sorted order, removing the need for a final sort.
**Cons:** The logic is less direct and might be slightly less intuitive than generating numbers from the given digits.; It iterates through all 450 possible 3-digit even numbers, even if the input digits cannot form any of them (e.g., `digits = [1,3,5]`).
### Explanation
This method works by first creating a frequency count of the available digits from the input array. An array of size 10, `digitCounts`, is ideal for this, where `digitCounts[i]` stores how many times digit `i` appears.

Next, we iterate through every even integer from 100 to 998. For each number in this range, we check if we have the necessary digits to form it. To do this, we determine the digits required for the current number. For example, the number 552 requires two '5's and one '2'.

We then compare the required digit counts with our available `digitCounts`. If for every digit (0-9), the count required is less than or equal to the count available, the number is valid and can be formed. We add such valid numbers to a result list.

Because we iterate through the candidate numbers in ascending order (100, 102, 104, ...), the final list of valid numbers will naturally be sorted. This eliminates the need for a separate sorting step.

```java
import java.util.*;

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

        List<Integer> resultList = new ArrayList<>();
        for (int num = 100; num <= 998; num += 2) {
            int d1 = num / 100;
            int d2 = (num / 10) % 10;
            int d3 = num % 10;

            int[] requiredCounts = new int[10];
            requiredCounts[d1]++;
            requiredCounts[d2]++;
            requiredCounts[d3]++;

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

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

        // Convert list to array
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}
```
### Algorithm
- Create a frequency map (an integer array of size 10) called `digitCounts` to store the counts of each digit in the input `digits` array.
- Initialize an empty list, `resultList`, to store the valid numbers.
- Iterate through all possible 3-digit even numbers. This can be done with a loop from `num = 100` to `998` with a step of 2.
- For each `num` in the loop:
  - Extract its three digits: `d1` (hundreds), `d2` (tens), and `d3` (units).
  - Create a frequency map for the digits of `num`, let's call it `requiredCounts`.
  - Check if `num` can be formed by comparing `requiredCounts` with `digitCounts`. For every digit from 0 to 9, the required count must be less than or equal to the available count (`requiredCounts[d] <= digitCounts[d]`).
  - If the number can be formed, add it to `resultList`.
- Since the loop iterates in increasing order, `resultList` will be sorted. Convert it to an integer array and return.

# Solutions
### Java

```java
class Solution {
public
  int totalNumbers(int[] digits) {
    Set<Integer> s = new HashSet<>();
    int n = digits.length;
    for (int i = 0; i < n; ++i) {
      if (digits[i] % 2 == 1) {
        continue;
      }
      for (int j = 0; j < n; ++j) {
        if (i == j) {
          continue;
        }
        for (int k = 0; k < n; ++k) {
          if (digits[k] == 0 || k == i || k == j) {
            continue;
          }
          s.add(digits[k] * 100 + digits[j] * 10 + digits[i]);
        }
      }
    }
    return s.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int totalNumbers(vector<int> &digits) {
    unordered_set<int> s;
    int n = digits.size();
    for (int i = 0; i < n; ++i) {
      if (digits[i] % 2 == 1) {
        continue;
      }
      for (int j = 0; j < n; ++j) {
        if (i == j) {
          continue;
        }
        for (int k = 0; k < n; ++k) {
          if (digits[k] == 0 || k == i || k == j) {
            continue;
          }
          s.insert(digits[k] * 100 + digits[j] * 10 + digits[i]);
        }
      }
    }
    return s.size();
  }
};

```

### Python

```python
class Solution:
    def totalNumbers(self, digits: List[int]) -> int: s = set() for i, a in enumerate(digits): if a & 1: continue for j, b in enumerate(digits): if i == j: continue for k, c in enumerate(digits): if c == 0 or k in (i, j): continue s . add(c * 100 + b * 10 + a) return len(s)

```