##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2094.html

# 2094. Finding 3-Digit Even Numbers (Easy)

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.


Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation:
The only valid integer that can be formed with three digits and no leading zeros is 200.


Example 5:

Input: digits = [0,0,0]
Output: []
Explanation:
All the integers that can be formed have leading zeros. Thus, there are no valid integers.


Constraints:

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

Similar Questions:

## Solution 1. Brute Force

// OJ: https://leetcode.com/problems/finding-3-digit-even-numbers/
// Time: O(N^3 * log(1000))
// Space: O(1000) = O(1)
class Solution {
public:
vector<int> findEvenNumbers(vector<int>& A) {
set<int> s;
int N = A.size();
for (int i = 0; i < N; ++i) {
if (A[i] == 0) continue;
for (int j = 0; j < N; ++j) {
if (i == j) continue;
for (int k = 0; k < N; ++k) {
if (k == i || k == j) continue;
if (A[k] % 2) continue;
s.insert(A[i] * 100 + A[j] * 10 + A[k]);
}
}
}
return vector<int>(begin(s), end(s));
}
};


## Solution 2. DFS

// OJ: https://leetcode.com/problems/finding-3-digit-even-numbers/
// Time: O(N + 10^3)
// Space: O(10) = O(1)
class Solution {
public:
vector<int> findEvenNumbers(vector<int>& A) {
int cnt[10] = {};
for (int n : A) cnt[n]++;
vector<int> ans;
function<void(int, int)> dfs = [&](int i, int n) {
if (i == 3) {
ans.push_back(n);
return;
}
for (int d = 0; d <= 9; ++d) {
if (cnt[d] == 0 || (i == 0 && d == 0) || (i == 2 && d % 2)) continue;
cnt[d]--;
dfs(i + 1, n * 10 + d);
cnt[d]++;
}
};
dfs(0, 0);
return ans;
}
};


## Solution 3. Counting

// OJ: https://leetcode.com/problems/finding-3-digit-even-numbers/
// Time: O(N + 10^3)
// Space: O(1)
class Solution {
public:
vector<int> findEvenNumbers(vector<int>& A) {
int cnt[10] = {};
for (int n : A) cnt[n]++;
vector<int> ans;
for (int n = 100; n < 1000; ++n) {
if (n % 2) continue;
int a = n / 100, b = n % 100 / 10, c = n % 10, used[10] = {};
used[a]++;
used[b]++;
used[c]++;
if (used[a] > cnt[a] || used[b] > cnt[b] || used[c] > cnt[c]) continue;
ans.push_back(n);
}
return ans;
}
};


## Solution 4.

// OJ: https://leetcode.com/problems/finding-3-digit-even-numbers/
// Time: O(N + 9 * 10 * 5)
// Space: O(1)
class Solution {
public:
vector<int> findEvenNumbers(vector<int>& A) {
int cnt[10] = {};
for (int n : A) cnt[n]++;
vector<int> ans;
for (int i = 1; i <= 9; ++i) {
if (cnt[i] == 0) continue;
for (int j = 0; j <= 9; ++j) {
if (cnt[j] - (i == j) == 0) continue;
for (int k = 0; k <= 8; k += 2) {
if (cnt[k] - (i == k) - (j == k) == 0) continue;
ans.push_back(i * 100 + j * 10 + k);
}
}
}
return ans;
}
};