Finding 3-Digit Even Numbers
EasyPrompt
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
digitsin 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.
Constraints:
3 <= digits.length <= 1000 <= digits[i] <= 9
Approaches
3 approaches with complexity analysis and trade-offs.
This approach generates all possible 3-digit numbers by picking three distinct digits from the input array. It uses three nested loops to iterate through all combinations of three indices, forms a number, and checks if it's a valid 3-digit even number without a leading zero. A HashSet is used to store the unique numbers, which are then sorted before being returned.
Algorithm
- Initialize a
Set<Integer>to store unique valid numbers, preventing duplicates. - Get the length of the input
digitsarray,n. - Use three nested loops with indices
i,j, andkto iterate from0ton-1. - Inside the innermost loop, check if the indices are distinct:
i != j,j != k, andi != k. - If the indices are distinct, retrieve the digits:
d1 = digits[i],d2 = digits[j],d3 = digits[k]. - Check if the formed number meets the problem's requirements:
- No leading zero:
d1 != 0. - Is an even number:
d3 % 2 == 0.
- No leading zero:
- If both conditions are met, form the number
num = d1 * 100 + d2 * 10 + d3and add it to theSet. - After the loops complete, convert the
Setinto an array. - Sort the resulting array in ascending order.
- Return the sorted array.
Walkthrough
The core idea is to exhaustively explore all permutations of size 3 from the given digits array. We can achieve this using three nested loops, where each loop iterates through the digits array to pick a digit for the hundreds, tens, and units place, respectively. To ensure we use three different elements from the array, we check that the indices i, j, and k are all distinct. For each valid combination of indices, we construct the number and verify two conditions: the first digit (from digits[i]) is not zero, and the last digit (from digits[k]) is even. Valid numbers are added to a HashSet to automatically handle uniqueness. Finally, the contents of the set are transferred to an array and sorted.
import java.util.*; class Solution { public int[] findEvenNumbers(int[] digits) { Set<Integer> resultSet = 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++) { if (i == j || j == k || i == k) { continue; } if (digits[i] != 0 && digits[k] % 2 == 0) { int num = digits[i] * 100 + digits[j] * 10 + digits[k]; resultSet.add(num); } } } } int[] result = new int[resultSet.size()]; int index = 0; for (int num : resultSet) { result[index++] = num; } Arrays.sort(result); return result; }}Complexity
Time
O(n^3 + K log K), where `n` is the length of the `digits` array and `K` is the number of unique valid numbers found. The three nested loops result in O(n^3) complexity. Sorting the final result adds O(K log K). Given `n <= 100`, this is feasible but slow.
Space
O(K), where K is the number of unique valid numbers. Since K is at most 450 (the number of 3-digit even numbers), the space complexity is effectively O(1), excluding the storage for the output array.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Correctly solves the problem for the given constraints.
Cons
Highly inefficient with a time complexity of O(n^3), which can be very slow if the input array size
nwere larger.Performs many redundant checks, especially when the input array contains duplicate digits.
Solutions
Solution
class Solution {public int[] findEvenNumbers(int[] digits) { int[] counter = count(digits); List<Integer> ans = new ArrayList<>(); for (int i = 100; i < 1000; i += 2) { int[] t = new int[3]; for (int j = 0, k = i; k > 0; ++j) { t[j] = k % 10; k /= 10; } int[] cnt = count(t); if (check(counter, cnt)) { ans.add(i); } } return ans.stream().mapToInt(Integer : : valueOf).toArray(); }private boolean check(int[] cnt1, int[] cnt2) { for (int i = 0; i < 10; ++i) { if (cnt1[i] < cnt2[i]) { return false; } } return true; }private int[] count(int[] nums) { int[] counter = new int[10]; for (int num : nums) { ++counter[num]; } return counter; }}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.