Unique 3-Digit Even Numbers
EasyPrompt
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] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
HashSet<Integer>to store the unique numbers found. - Use three nested loops, with indices
i,j, andk, to iterate through all combinations of three positions in thedigitsarray. - Inside the innermost loop, check if the indices
i,j, andkare 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
d1must not be 0 (to avoid numbers less than 100). - The last digit
d3must be even (d3 % 2 == 0).
- The first digit
- If both conditions are met, form the number
num = d1 * 100 + d2 * 10 + d3and add it to theHashSet. - After the loops complete, convert the set to an array and sort it to get the final result.
Walkthrough
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:
digits[i](the hundreds digit) cannot be zero.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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.