2094

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:

• Find Numbers with Even Number of Digits (Easy)

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/finding-3-digit-even-numbers/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};