Finding 3-Digit Even Numbers

EASY

Description

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.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Approaches

Checkout 3 different approaches to solve Finding 3-Digit Even Numbers. Click on different approaches to view the approach and algorithm in detail.

Brute-Force with Nested Loops

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 digits array, n.
Use three nested loops with indices i, j, and k to iterate from 0 to n-1.
Inside the innermost loop, check if the indices are distinct: i != j, j != k, and i != 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.
If both conditions are met, form the number num = d1 * 100 + d2 * 10 + d3 and add it to the Set.
After the loops complete, convert the Set into an array.
Sort the resulting array in ascending order.
Return the sorted array.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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 n were larger.
Performs many redundant checks, especially when the input array contains duplicate digits.

Code Solutions

Checking out 4 solutions in different languages for Finding 3-Digit Even Numbers. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Finding 3-Digit Even Numbers

Algorithms:

Sorting

Patterns:

Enumeration

Data Structures:

ArrayHash Table