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

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3

Input: digits = [6,6,6]
Output: 1
Explanation: Only 666 can be formed.

Example 4

1
2
3

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

Examples

Solution

Method 1 – Brute Force with Set

Intuition

Try all possible 3-digit numbers using the digits, check if they are even, have no leading zero, and can be formed with the available digits.

Approach

  1. Generate all 3-digit numbers from 100 to 998 (step 2).
  2. For each, check if all digits are in the input and used at most as many times as available.
  3. Use a set to ensure uniqueness.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int countEvenNumbers(vector<int>& digits) {
    unordered_map<int, int> cnt;
    for (int d : digits) cnt[d]++;
    unordered_set<int> res;
    for (int i = 100; i < 1000; i += 2) {
        int a = i / 100, b = (i / 10) % 10, c = i % 10;
        unordered_map<int, int> need;
        need[a]++; need[b]++; need[c]++;
        bool ok = true;
        for (auto& [d, v] : need) {
            if (cnt[d] < v) { ok = false; break; }
        }
        if (ok) res.insert(i);
    }
    return res.size();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;
class Solution {
    public int countEvenNumbers(int[] digits) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int d : digits) cnt.put(d, cnt.getOrDefault(d, 0) + 1);
        Set<Integer> res = new HashSet<>();
        for (int i = 100; i < 1000; i += 2) {
            int a = i / 100, b = (i / 10) % 10, c = i % 10;
            Map<Integer, Integer> need = new HashMap<>();
            need.put(a, need.getOrDefault(a, 0) + 1);
            need.put(b, need.getOrDefault(b, 0) + 1);
            need.put(c, need.getOrDefault(c, 0) + 1);
            boolean ok = true;
            for (int d : need.keySet()) {
                if (cnt.getOrDefault(d, 0) < need.get(d)) { ok = false; break; }
            }
            if (ok) res.add(i);
        }
        return res.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def countEvenNumbers(digits):
    from collections import Counter
    cnt = Counter(digits)
    res = set()
    for i in range(100, 1000, 2):
        d = [i // 100, (i // 10) % 10, i % 10]
        need = Counter(d)
        if all(cnt[x] >= need[x] for x in need):
            res.add(i)
    return len(res)

Complexity

  • ⏰ Time complexity: O(1) — Only 450 numbers checked, each check is O(1).
  • 🧺 Space complexity: O(1) — At most 450 numbers in the set.