Problem Informations

• Problem Index: 2094
• Problem Link: Finding 3-Digit Even Numbers
• Topics: Array, Hash Table, Sorting, Enumeration

Problem 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 \leq \text{digits.length} \leq 100$
• $0 \leq \text{digits}[i] \leq 9$

Intuition

The problem requires generating all unique three-digit even numbers using the given digits. This involves a combinatorial approach where we should systematically consider all possible permutations of the digits to form valid numbers that meet the criteria: three digits, even, and no leading zeros. Given the constraints, a direct approach of checking all possible three-digit numbers is feasible.

Approach

The provided solution employs a systematic method to check each possible three-digit even number within the range from 100 to 998. The algorithm constructs these numbers and verifies if they can be formed using the digits from the input array based on the following steps:

1. Digit Frequency Count:

   • First, we build a frequency array, digitCount, which counts the occurrences of each digit (0-9) in the input array digits. This helps in quickly verifying if a required digit for forming a number is available.

2. Iterate Over Possible Numbers:

   • The algorithm iterates through all possible three-digit even numbers, starting from 100 to 998, incrementing by 2 (ensuring the number is even).

3. Extract Digits of Each Candidate Number:

   • For each candidate number, extract its hundreds, tens, and units digits. This is done using arithmetic operations:
     • Hundreds digit: $\text{number} / 100$
     • Tens digit: $(\text{number} / 10) % 10$
     • Units digit: $\text{number} % 10$

4. Check Formability Using Digit Frequency:

   • For each digit extracted, maintain a frequency count (needed) to determine how many times each digit is required to form the current candidate number.
   • Compare this required frequency with the available frequency (digitCount) from the input. If any required digit count exceeds the available count, the number cannot be formed.

5. Collect Valid Numbers:

   • If a candidate number can be formed with the given digit availability (i.e., canFormNumber remains true), it is added to the result list.

6. Return the Result:

   • The result vector, containing all valid, unique, and sorted even numbers, is returned as the final output.

This brute-force approach is efficient within the problem’s constraints, as it interacts with a manageable range of numbers (450 possible even numbers) and leverages direct frequency matching to confirm valid constructs.

Code

C++

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        // Frequency array to count each digit from 0 to 9 in `digits`
        vector<int> digitCount(10, 0);
        for (int digit : digits) {
            ++digitCount[digit];
        }

        vector<int> result;
        
        // Iterate through all 3-digit even numbers from 100 to 998
        for (int number = 100; number <= 998; number += 2) {
            // Extract hundreds, tens, and units place digits
            int hundreds = number / 100;
            int tens = (number / 10) % 10;
            int units = number % 10;

            // Frequency array for the current number
            vector<int> needed(10, 0);
            ++needed[hundreds];
            ++needed[tens];
            ++needed[units];

            // Check if the current number can be formed with the available digits
            bool canFormNumber = true;
            if (needed[hundreds] > digitCount[hundreds] ||
                needed[tens] > digitCount[tens] ||
                needed[units] > digitCount[units]) {
                canFormNumber = false;
            }

            // If the number can be formed, add it to the result vector
            if (canFormNumber) {
                result.push_back(number);
            }
        }

        return result;
    }
};

Python

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        # Frequency array to count each digit from 0 to 9 in `digits`
        digitCount = [0] * 10
        for digit in digits:
            digitCount[digit] += 1

        result = []
        
        # Iterate through all 3-digit even numbers from 100 to 998
        for number in range(100, 999, 2):
            # Extract hundreds, tens, and units place digits
            hundreds = number // 100
            tens = (number // 10) % 10
            units = number % 10

            # Frequency array for the current number
            needed = [0] * 10
            needed[hundreds] += 1
            needed[tens] += 1
            needed[units] += 1

            # Check if the current number can be formed with the available digits
            canFormNumber = True
            if (needed[hundreds] > digitCount[hundreds] or
                needed[tens] > digitCount[tens] or
                needed[units] > digitCount[units]):
                canFormNumber = False

            # If the number can be formed, add it to the result vector
            if canFormNumber:
                result.append(number)

        return result

Complexity

• Time complexity: $O(1)$

  The algorithm iterates through all possible three-digit even numbers from 100 to 998, which is a constant number of operations (450 iterations). Within each iteration, it performs a fixed amount of work including extracting digits and checking conditions, thus the time complexity is $O(1)$ for practical purposes given the constraints.

• Space complexity: $O(1)$

  Regardless of the input size due to constraints, the algorithm maintains a fixed-size frequency array, both for digit count and needed digit count. The space used does not scale with input size, thus making the space complexity $O(1)$.