algoadvance

Leetcode 2094. Finding 3

Problem Statement

You are given an integer array digits, where each element is a digit (0 - 9). The task is to return a sorted list of all unique 3-digit even numbers that can be formed using the digits in the array. Each digit from the array can only be used at most once in each 3-digit number.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the array?
    • Will there always be at least three digits in the array?

    Constraints according to the problem:

    • The array length is between 3 and 100.
    • Each digit is between 0 and 9.
    • There might be duplicate digits.
  2. Output Constraints:
    • Should the output list be sorted in ascending order?
    • Do we need to return the list of digits in a specific format?

    Output according to the problem:

    • The output should be a list of integers, sorted in ascending order.
  3. Additional Clarification:
    • Can the 3-digit number start with zero?
      • No, it should be a valid 3-digit number so it cannot start with zero.

Strategy

  1. Combinations:
    • Generate all possible 3-digit numbers using a nested loop to pick one digit for the hundreds place, one for the tens place, and one for the units place.
  2. Validation:
    • The hundreds place digit should not be zero.
    • The units place digit should be even.
  3. Uniqueness:
    • Store the valid combinations in a set to handle uniqueness.
  4. Sorting:
    • Convert the set to a list and sort it in ascending order.

Time Complexity

Given the constraints, this approach should be efficient and feasible.

Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

std::vector<int> findEvenNumbers(std::vector<int>& digits) {
    std::set<int> unique_even_numbers;
    int n = digits.size();
    
    for (int i = 0; i < n; ++i) {
        if (digits[i] == 0) continue;  // Skip zero for the hundreds place
        for (int j = 0; j < n; ++j) {
            if (j == i) continue;  // Same index as the hundreds place
            for (int k = 0; k < n; ++k) {
                if (k == i || k == j) continue;  // Same index as the hundreds or tens place
                if (digits[k] % 2 == 0) { // Units place must be even
                    int number = digits[i] * 100 + digits[j] * 10 + digits[k];
                    unique_even_numbers.insert(number);
                }
            }
        }
    }
    
    // Convert set to vector and sort
    std::vector<int> result(unique_even_numbers.begin(), unique_even_numbers.end());
    return result;
}

int main() {
    std::vector<int> digits = {2, 1, 3, 0};
    std::vector<int> result = findEvenNumbers(digits);
    for (int num : result) {
        std::cout << num << " ";
    }
    return 0;
}

This code effectively iterates through all combinations of three digits, ensuring the hundreds place is non-zero, the units place is even, and all digits are unique to the combination. These numbers are stored in a set to handle duplicates, and the final sorted list of unique 3-digit even numbers is returned.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI