algoadvance

Given an integer array digits where each element is a digit from 0 to 9, you need to find all the unique 3-digit even numbers that can be formed using exactly three of the given digits in digits. Return the numbers in ascending order as a sorted list.

Clarifying Questions

  1. Can we use the same digit more than once?
    • No, each digit should be used exactly once.
  2. What is the expected return type?
    • The function should return a list of integers.
  3. What if the input array has less than 3 digits?
    • If the input array has less than 3 digits, it is impossible to form a 3-digit number, hence the output should be an empty list.
  4. Can the input array contain duplicate digits?
    • Yes, the input array may contain duplicates, but each digit should be used only once per 3-digit number formation.

Strategy

  1. Filtering for Valid Combinations:
    • Since the number has to be even, the last digit must be even. We will filter combinations based on this condition.
  2. Generate Combinations:
    • Use permutations to generate all possible 3-digit combinations from the given digits.
  3. Check Validity and Uniqueness:
    • Filter valid 3-digit numbers where the last digit is even.
    • Ensure numbers are unique by using a set.
  4. Sorting:
    • Convert the set to a sorted list and return it.
  5. Edge Cases:
    • Handle cases where there are less than 3 digits in the input array.
    • Handle cases with repeated digits.

Time Complexity

Code

Here is the implementation based on the strategy:

from itertools import permutations

def findEvenNumbers(digits):
    # Convert permutations of digits into potential 3-digit numbers
    unique_numbers = set()
    
    for perm in permutations(digits, 3):
        # Check if last digit is even
        if perm[2] % 2 == 0:
            number = perm[0] * 100 + perm[1] * 10 + perm[2]
            # Ensure it is a 3-digit number (first digit must not be zero)
            if perm[0] != 0:
                unique_numbers.add(number)
    
    # Sort the unique numbers and return them as a list
    return sorted(unique_numbers)

# Example usage
digits = [2, 1, 3, 0]
print(findEvenNumbers(digits))  # Output: [102, 120, 130, 132, 210, 230, 302, 310, 312, 320]

Now, this function findEvenNumbers will generate and return all unique 3-digit even numbers that can be formed from the given digits, in ascending order.

Try our interview co-pilot at AlgoAdvance.com