Watch 5 video solutions for Unique 3-Digit Even Numbers, a easy level problem involving Array, Hash Table, Recursion. This walkthrough by Kabil Bano has 935 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100 <= digits[i] <= 9Problem Overview: You are given an array of digits. The task is to form all possible unique three-digit even numbers using these digits, where each digit index can be used at most once. The number cannot start with 0, and the last digit must be even.
Approach 1: Brute Force Permutation (O(n^3) time, O(k) space)
Generate every ordered triple of indices (i, j, k) from the digits array. Each triple represents a three-digit number digits[i] * 100 + digits[j] * 10 + digits[k]. Apply the constraints while iterating: the first digit cannot be 0, and the last digit must be even. Since different index combinations can produce the same number, store valid results in a HashSet to keep them unique. This approach is straightforward because the number has fixed length (3), so checking every combination is feasible.
The algorithm runs three nested loops over the input array, giving O(n^3) time complexity. The set storing valid numbers takes O(k) space where k is the number of valid results (at most a few hundred). This brute-force enumeration works well because the search space is small.
Approach 2: Hash Set + Enumeration (O(n^3) time, O(k) space)
A cleaner implementation still enumerates digit positions but focuses on building the number directly while enforcing constraints early. Iterate over all possible first digits from the array, skipping 0. For the second digit, iterate again while ensuring a different index is used. For the third digit, only consider digits that are even (0,2,4,6,8). Construct the number and insert it into a HashSet to avoid duplicates.
The key idea is pruning invalid candidates during enumeration instead of generating all permutations first. By filtering on the last digit being even and preventing leading zeros, unnecessary checks are avoided. The final result can be returned as a sorted list of the unique values from the set.
This technique is essentially controlled enumeration combined with constant-time duplicate removal using a hash table. The digits are stored in an array, and iteration builds valid candidates efficiently.
Recommended for interviews: The Hash Set + Enumeration approach is what most interviewers expect. It demonstrates that you understand constraint filtering (no leading zero, even last digit) and how to guarantee uniqueness using a hash set. A naive permutation discussion shows baseline reasoning, but the enumeration approach with pruning and hashing signals stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation | O(n^3) | O(k) | Small input sizes where generating all index combinations is simple and easy to implement |
| Hash Set + Enumeration | O(n^3) | O(k) | Best general approach. Filters invalid candidates early and guarantees uniqueness with a hash set |