We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Finding 3-Digit Even Numbers

Number: 2215

Difficulty: Easy

Paid? No

Companies: Google, Amazon

Problem Description

Given an integer array of digits, form all unique 3-digit numbers by concatenating any three digits from the array. The number must not have a leading zero and must be even. Return the resulting numbers in sorted order.

Key Insights

  • Permutations of three digits must be considered, but duplicates in the output should be avoided.
  • The hundreds digit (first digit) cannot be zero.
  • The units digit (last digit) must be even.
  • Brute force enumeration (using three nested loops or permutation generation) is acceptable given the input constraints.

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case scenario, where n is the number of digits. Space Complexity: O(k), where k is the number of valid 3-digit numbers stored.

Solution

We iterate through every possible combination of three digits (taking into account their indices to avoid using the same digit more times than allowed). For each combination:

  1. Check that the first digit is not zero to avoid a leading zero.
  2. Ensure that the final digit is even (i.e., 0, 2, 4, 6, or 8). If both conditions are met, combine the digits into a 3-digit number and add it to a set to ensure uniqueness. Finally, convert the set into a sorted list and return it. Data structures used include a set for unique values, and simple loops for enumeration.

Code Solutions

def findEvenNumbers(digits):
    # Set to store unique valid numbers
    valid_numbers = set()
    n = len(digits)
    # Iterate over all possible index triples
    for i in range(n):
        for j in range(n):
            for k in range(n):
                # Ensure indices are distinct
                if i == j or i == k or j == k:
                    continue
                # Check no leading zero and even last digit
                if digits[i] == 0 or digits[k] % 2 != 0:
                    continue
                # Form the number as a 3-digit integer
                number = digits[i] * 100 + digits[j] * 10 + digits[k]
                valid_numbers.add(number)
    # Return sorted list of unique numbers
    return sorted(valid_numbers)

# Example usage:
digits = [2, 1, 3, 0]
print(findEvenNumbers(digits))  # Expected output: [102, 120, 130, 132, 210, 230, 302, 310, 312, 320]
← Back to All Questions