Problem Description

You are given an array of digits (0-9) and need to find how many distinct three-digit even numbers can be formed using these digits.

The key constraints are:

• The number must be a valid three-digit number (100-999), so it cannot have leading zeros
• The number must be even (last digit must be 0, 2, 4, 6, or 8)
• Each digit from the array can be used at most once per number (if a digit appears multiple times in the array, each occurrence is treated as a separate digit that can be used)
• You need to count only distinct numbers (no duplicates)

For example, if you have digits [1, 2, 3, 4], you could form numbers like:

• 132 (even, ends with 2)
• 124 (even, ends with 4)
• 312 (even, ends with 2)
• And so on...

The solution uses three nested loops to enumerate all possible combinations:

1. The outer loop picks the last digit (must be even for the number to be even)
2. The middle loop picks the middle digit (cannot be the same position as the last digit)
3. The inner loop picks the first digit (cannot be 0 for a valid three-digit number, and cannot use positions already taken)

The number is constructed as c * 100 + b * 10 + a where c is the hundreds digit, b is the tens digit, and a is the units digit. A set is used to automatically handle duplicates, ensuring only distinct numbers are counted.

Intuition

To form a valid three-digit even number, we need to think about the constraints for each position:

1. Units place (rightmost digit): Must be even (0, 2, 4, 6, or 8) for the entire number to be even
2. Hundreds place (leftmost digit): Cannot be 0 (otherwise it wouldn't be a three-digit number)
3. Tens place (middle digit): Can be any digit from 0-9

Since we need to count distinct numbers and each digit position in the array can only be used once, we face a selection problem. We're essentially picking 3 positions from the array to form our number, with specific constraints on what values those positions can have.

The natural approach is to enumerate all valid combinations. We start by fixing the units digit (checking if it's even), then try all possible tens digits (avoiding the position we already used), and finally try all possible hundreds digits (avoiding both previously used positions and the value 0).

Why use a hash set? As we generate numbers, the same three-digit number might be formed from different combinations of array positions. For instance, if the array is [1, 2, 1, 2], we could form 212 using positions (0, 1, 3) or positions (2, 1, 3). The set automatically handles this deduplication for us.

The key insight is that we're not just looking at the values in the array, but at the positions of those values. This is why the solution uses indices i, j, k to ensure we don't reuse the same position, even if the same digit value appears multiple times in the array.

Learn more about Recursion patterns.

Solution Approach

The solution uses a hash set with enumeration approach to find all distinct three-digit even numbers.

Data Structure Used:

• A hash set s to store distinct three-digit numbers and automatically handle duplicates

Algorithm Steps:

1. Initialize an empty set s to store distinct numbers.

2. First loop - Fix the units digit: Iterate through each digit at position i in the array:

   • Check if the digit a is even using bitwise AND: if a & 1 (if the result is 1, the number is odd, so we skip it)
   • If odd, continue to the next iteration
   • If even, this digit can be our units place

3. Second loop - Fix the tens digit: For each valid units digit, iterate through all positions j:

   • Skip if i == j (can't reuse the same position)
   • The digit b at position j becomes our tens digit

4. Third loop - Fix the hundreds digit: For each valid units and tens combination, iterate through all positions k:

   • Check two conditions:
     • c == 0: Skip if the digit is 0 (no leading zeros allowed)
     • k in (i, j): Skip if position k is already used
   • If valid, the digit c at position k becomes our hundreds digit

5. Form the number and add to set:

   • Calculate the three-digit number as c * 100 + b * 10 + a
   • Add it to the set (duplicates are automatically ignored)

6. Return the count: Return len(s), which gives us the total number of distinct three-digit even numbers.

Time Complexity: O(n³) where n is the length of the digits array, as we have three nested loops.

Space Complexity: O(m) where m is the number of distinct three-digit even numbers that can be formed (at most 450 for even numbers from 100-998).

Example Walkthrough

Let's walk through the solution with the array digits = [2, 1, 3, 0].

Step 1: Initialize empty set

• s = {}

Step 2: Iterate through positions for units digit (must be even)

When i = 0 (digit = 2, even ✓):

• j = 1 (digit = 1):
  • k = 2 (digit = 3): Form 312 → Add to set
  • k = 3 (digit = 0): Skip (0 cannot be hundreds digit)
• j = 2 (digit = 3):
  • k = 1 (digit = 1): Form 132 → Add to set
  • k = 3 (digit = 0): Skip (0 cannot be hundreds digit)
• j = 3 (digit = 0):
  • k = 1 (digit = 1): Form 102 → Add to set
  • k = 2 (digit = 3): Form 302 → Add to set

When i = 1 (digit = 1, odd):

• Skip (not even)

When i = 2 (digit = 3, odd):

• Skip (not even)

When i = 3 (digit = 0, even ✓):

• j = 0 (digit = 2):
  • k = 1 (digit = 1): Form 120 → Add to set
  • k = 2 (digit = 3): Form 320 → Add to set
• j = 1 (digit = 1):
  • k = 0 (digit = 2): Form 210 → Add to set
  • k = 2 (digit = 3): Form 310 → Add to set
• j = 2 (digit = 3):
  • k = 0 (digit = 2): Form 230 → Add to set
  • k = 1 (digit = 1): Form 130 → Add to set

Step 3: Count distinct numbers

• Final set: {312, 132, 102, 302, 120, 320, 210, 310, 230, 130}
• Return len(s) = 10

The algorithm successfully finds all 10 distinct three-digit even numbers that can be formed from the digits [2, 1, 3, 0].

Solution Implementation

Time and Space Complexity

The time complexity is O(n³), where n is the length of the array digits.

This is because the code contains three nested loops:

• The outer loop iterates through all digits (n iterations)
• The middle loop iterates through all digits (n iterations)
• The inner loop iterates through all digits (n iterations)

Even though there are early continue statements that skip some iterations (when a is odd, when i == j, or when c == 0 or k is in (i, j)), these conditions only affect constant factors. In the worst case, we still need to examine all possible combinations of three positions from the array, resulting in O(n³) time complexity.

The space complexity is O(n³), where n is the length of the array digits.

The set s stores unique three-digit numbers formed by the digits. In the worst case, if all digits are distinct and meet the conditions (even last digit, non-zero first digit), we could potentially store up to O(n³) unique three-digit numbers in the set. Each unique combination of three positions with valid digits creates a distinct number that gets added to the set.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing digit value with array index

A frequent mistake is treating the digit positions and digit values interchangeably. The code correctly uses indices to track which positions in the array have been used, but developers often mistakenly compare digit values instead of indices.

Incorrect approach:

# Wrong: comparing digit values instead of indices
if hundreds_digit == ones_digit or hundreds_digit == tens_digit:
    continue

Correct approach:

# Right: comparing indices to ensure each position is used only once
if hundreds_index in (ones_index, tens_index):
    continue

2. Incorrectly checking for even numbers

Some developers check evenness of the wrong digit or place the check in the wrong position.

Incorrect approach:

# Wrong: checking evenness after forming the number
number = hundreds_digit * 100 + tens_digit * 10 + ones_digit
if number % 2 == 0:
    unique_numbers.add(number)

Correct approach:

# Right: check ones digit for evenness before proceeding
if ones_digit & 1:  # Skip odd digits
    continue

3. Allowing duplicate digits when the array has duplicates

If the input array is [2, 2, 8, 8, 2], each occurrence is a separate digit that can be used. However, a common mistake is to deduplicate the input array first, which would incorrectly reduce the number of possible combinations.

Incorrect approach:

# Wrong: removing duplicates from input
digits = list(set(digits))  # This loses valid digit occurrences

Correct approach:

# Right: treat each array element as a separate digit
for ones_index, ones_digit in enumerate(digits):
    # Each index represents a unique position, even if values are the same

4. Using the wrong data structure for storing results

Using a list instead of a set would require manual duplicate checking, making the code more complex and error-prone.

Incorrect approach:

# Wrong: using list and manual duplicate checking
result = []
number = hundreds_digit * 100 + tens_digit * 10 + ones_digit
if number not in result:  # O(n) check each time
    result.append(number)

Correct approach:

# Right: using set for automatic duplicate handling
unique_numbers = set()
unique_numbers.add(number)  # O(1) operation with automatic deduplication