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

Unique 3-Digit Even Numbers

Number: 3799

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of digits, determine the number of distinct three-digit even numbers that can be formed by using these digits. Each occurrence of a digit in the array can be used at most once per number, numbers cannot have leading zeros, and the number must be even (i.e., its last digit is even).

Key Insights

  • The first digit (hundreds place) cannot be zero to avoid leading zeros.
  • The last digit must be even.
  • We must consider each unique permutation of three digits that satisfies the above conditions.
  • Use a set to ensure uniqueness since duplicate digits can lead to repeated values.
  • Given the small input size, a brute-force approach utilizing three nested loops (or recursion with backtracking) is acceptable.

Space and Time Complexity

Time Complexity: O(n^3) where n is the number of digits, due to iterating through all possible triplets. Space Complexity: O(1) or O(m) where m is the number of valid numbers stored in the set, which is bounded by a constant (at most 900 numbers).

Solution

The solution involves enumerating every permutation of three different indices in the provided digits array. For each permutation, we ensure that:

  • The first digit is not zero.
  • The last digit is even. If these conditions are met, we form the three-digit number and insert it into a set to avoid counting duplicates. Finally, we return the count of unique numbers in this set.

Code Solutions

# Define the function to count valid three-digit even numbers
def countEvenNumbers(digits):
    valid_numbers = set()  # Set to hold unique valid numbers
    n = len(digits)
    # Iterate over each digit for the hundreds place
    for i in range(n):
        if digits[i] == 0:  # Skip leading zero
            continue
        # Iterate over each digit for the tens place
        for j in range(n):
            if i == j:  # Ensure different digit usage
                continue
            # Iterate over each digit for the ones place
            for k in range(n):
                if k == i or k == j:  # Ensure unique indices
                    continue
                if digits[k] % 2 == 0:  # Last digit must be even
                    number = digits[i] * 100 + digits[j] * 10 + digits[k]
                    valid_numbers.add(number)
    return len(valid_numbers)

# Example usage:
print(countEvenNumbers([1,2,3,4]))  # Expected output: 12
← Back to All Questions