Problem

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.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
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

Solution

Method 1 - Generating combinations

To address the problem, let’s break it into steps:

  1. Generate combinations: Create all possible combinations of three distinct digits from the given array.
  2. Concatenate digits: For each combination, concatenate the digits in all possible orders. This results in integers formed by concatenating three digits.
  3. Check requirements:
    • Ensure integers do not have leading zeros.
    • Ensure integers are even (last digit is divisible by 2).
  4. Remove duplicates: Use a set data structure to ensure uniqueness of integers.
  5. Sort the result: Return the sorted list of integers.

Code

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

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> ans = new HashSet<>(); // Store unique integers
        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) {  // Ensure distinct indices
                        int num = digits[i] * 100 + digits[j] * 10 + digits[k];
                        if (digits[i] != 0 && num % 2 == 0) { // No leading zero and even
                            ans.add(num);
                        }
                    }
                }
            }
        }
        
        int[] result = ans.stream().sorted().mapToInt(x -> x).toArray(); // Convert set to sorted array
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        from itertools import permutations
        
        ans: set[int] = set()  # Store unique integers
        n = len(digits)
        
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i != j and j != k and i != k:  # Ensure distinct indices
                        num = digits[i] * 100 + digits[j] * 10 + digits[k]
                        if digits[i] != 0 and num % 2 == 0:  # No leading zero and even
                            ans.add(num)
        
        return sorted(ans)

Complexity

  • ⏰ Time complexity: O(n^3 × 3!), where n is the number of digits in the input array.
    • Generating combinations takes O(n^3) since we pick three distinct digits.
    • Permutation generation for each combination takes O(3!) = O(6).
    • Filtering conditions are O(1) per integer.
  • 🧺 Space complexity: O(k), where k is the number of valid integers in the output.