Finding 3-Digit Even Numbers

Problem Statement

You are given an integer array digits, where each element is digit. The array may contains 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 zeroes.
• 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:

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 zeroes.

Example 2:

Input: digits = [2, 2, 8, 8, 2]
Output: [
         222,
         228,
         282,
         288,
         822,
         828,
         882
        ]

Example: 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, 882.

Example 3:

Input: digits = [3, 7, 5]
Output: []

Explanation:
No even integers can be formed using the given digits.

Different Approaches

1️⃣ Brute Force Approach

🛠️ Approach:

1. Try all 3-digit permutations (with different indices):
   • Use 3 nested loops over the indices of digits.
   • Ensure indices i, j, k are distinct.
   • Form the number: num = digits[i]*100 + digits[j]*10 + digits[k].
2. Apply constraints:
   • Skip if the hundreds digit is 0 (i.e., not a 3-digit number).
   • Skip if the units digit is odd (i.e., not even).
3. Use a set or bool array to avoid duplicates:
   • Because different permutations can lead to the same number.
4. Collect results and return them in sorted order.

Code:

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        int n = digits.size();
        unordered_set<int> validNumbers;  // To store unique valid 3-digit even numbers

        // Step 1: Try all permutations of 3 different indices
        for (int first = 0; first < n; first++) {
            for (int second = 0; second < n; second++) {
                for (int third = 0; third < n; third++) {

                    // Step 2: Ensure all indices are distinct
                    if (first != second && second != third && third != first) {
                        int hundreds = digits[first];
                        int tens = digits[second];
                        int units = digits[third];

                        int number = hundreds * 100 + tens * 10 + units;

                        // Step 3: Check if number is a valid 3-digit even number
                        if (hundreds != 0 && number % 2 == 0) {
                            validNumbers.insert(number);
                        }
                    }
                }
            }
        }

        // Step 4: Copy set into vector and sort the results
        vector<int> result(validNumbers.begin(), validNumbers.end());
        sort(result.begin(), result.end());

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n^3 + k log k)
  • O(n^3) for trying all 3-digit combinations.
  • Sorting at the end: O(k log k), where k is the number of valid numbers.
• Space Complexity: O(k)
  • For result storage.

2️⃣ Digit Frequency

🔢 Approach:

1. Frequency Count:

   • Count how many times each digit (0 to 9) appears in the input using an array freq[10].

2. Try All Valid 3-Digit Even Numbers:

   • Loop firstDigit from 1 to 9 → to ensure number doesn't start with 0.

   • Loop secondDigit from 0 to 9 → any digit can be at the middle.

   • Loop thirdDigit from 0 to 8 (step 2) → only even digits are allowed at the end.

3. Check Availability:

   • Before forming the number, ensure all three digits are available using the freq array.

   • Temporarily decrease their frequencies (to simulate usage), then backtrack.

4. Form the Number and Store:

   • Construct the number using the 3 digits: 100*a + 10*b + c.

   • Push it to the result list.

Code:

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> result;

        // Step 1: Create a frequency array to count how many times each digit (0-9) appears
        vector<int> freq(10, 0);
        for (int digit : digits) {
            freq[digit]++;
        }

        // Step 2: Try every valid 3-digit even number
        // The number must be in the form: [firstDigit][secondDigit][thirdDigit]
        // where:
        //   - firstDigit: cannot be 0 (to make it a 3-digit number)
        //   - thirdDigit: must be even (0, 2, 4, 6, 8)

        for (int firstDigit = 1; firstDigit <= 9; ++firstDigit) {
            // Skip if the first digit is not available in digits
            if (freq[firstDigit] == 0) continue;
            freq[firstDigit]--; // use this digit

            for (int secondDigit = 0; secondDigit <= 9; ++secondDigit) {
                // Skip if the second digit is not available
                if (freq[secondDigit] == 0) continue;
                freq[secondDigit]--; // use this digit

                // Only even digits can be at the end of the number
                for (int thirdDigit = 0; thirdDigit <= 8; thirdDigit += 2) {
                    // Skip if the third digit (even) is not available
                    if (freq[thirdDigit] == 0) continue;
                    freq[thirdDigit]--; // use this digit

                    // Step 3: Construct the 3-digit number and store it
                    int number = firstDigit * 100 + secondDigit * 10 + thirdDigit;
                    result.push_back(number);

                    freq[thirdDigit]++; // backtrack: restore third digit count
                }

                freq[secondDigit]++; // backtrack: restore second digit count
            }

            freq[firstDigit]++; // backtrack: restore first digit count
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(1)
• Space Complexity: O(1)