Unique 3-Digit Even Numbers

Difficulty: Easy | Acceptance: 69.70% | Paid: No Topics: Array, Hash Table, Recursion, Enumeration

You are given an integer array digits, where each element is a digit (0-9). The digits may contain duplicates. Return the count of all unique 3-digit even numbers that can be formed from the digits in digits.

A 3-digit number is a number from 100 to 999. A number is even if its last digit is 0, 2, 4, 6, or 8. Each digit in digits can be used at most once in a number.

• Examples
• Constraints
• Approach 1: Brute Force with HashSet
• Approach 2: Backtracking
• Approach 3: Frequency Counting

Examples

Example 1

Input:

digits = [1,2,3,4]

Output:

12

Explanation: The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2.

Example 2

Input:

digits = [0,2,2]

Output:

2

Explanation: The only 3-digit even numbers that can be formed are 202 and 220. Note that the digit 2 can be used twice because it appears twice in the array.

Example 3

Input:

digits = [6,6,6]

Output:

1

Explanation: Only 666 can be formed.

Example 4

Input:

digits = [1,3,5]

Output:

0

Explanation: No even 3-digit numbers can be formed.

Constraints

3 <= digits.length <= 10
0 <= digits[i] <= 9

Approach 1: Brute Force with HashSet

Intuition We can generate all possible combinations of 3 digits from the array using three nested loops. For each combination, we check if it forms a valid 3-digit even number (hundreds digit != 0, units digit is even). We store valid numbers in a HashSet to automatically handle duplicates.

Steps

• Initialize an empty HashSet to store unique numbers.
• Iterate through the array with three indices i, j, and k to select the hundreds, tens, and units digits respectively.
• Ensure i, j, and k are distinct indices.
• Check if digits[i] is not 0 (to ensure it is a 3-digit number) and digits[k] is even.
• Construct the number: digits[i] * 100 + digits[j] * 10 + digits[k].
• Add the number to the HashSet.
• Return the size of the HashSet.

class Solution:
    def findEvenNumbers(self, digits: list[int]) -> int:
        unique_numbers = set()
        n = len(digits)
        
        for i in range(n):
            if digits[i] == 0:
                continue
            for j in range(n):
                if i == j:
                    continue
                for k in range(n):
                    if k == i or k == j:
                        continue
                    if digits[k] % 2 == 0:
                        num = digits[i] * 100 + digits[j] * 10 + digits[k]
                        unique_numbers.add(num)
                        
        return len(unique_numbers)

Complexity

• Time: O(n³) where n is the length of digits. Since n <= 10, this is effectively O(1).
• Space: O(1) to store the results (max 900 possible 3-digit numbers).
• Notes: Simple and readable, perfectly efficient given the small constraints.

Approach 2: Backtracking

Intuition We can use recursion to explore all permutations of length 3. This approach builds the number digit by digit, keeping track of which indices have been used. It naturally handles the “use each digit at most once” rule.

Steps

• Initialize a HashSet to store results.
• Define a recursive function that takes the current number being built and a boolean array (or bitmask) tracking used indices.
• Base case: If the number has 3 digits, check if it is >= 100 and even. If so, add to the set.
• Recursive step: Iterate through all digits. If a digit is not used, add it to the current number, mark it as used, and recurse.
• Backtrack: Unmark the digit as used and remove it from the current number.

class Solution:
    def findEvenNumbers(self, digits: list[int]) -> int:
        res = set()
        n = len(digits)
        
        def backtrack(curr, used):
            if len(curr) == 3:
                if curr[0] != 0 and curr[2] % 2 == 0:
                    num = curr[0] * 100 + curr[1] * 10 + curr[2]
                    res.add(num)
                return
            
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    backtrack(curr + [digits[i]], used)
                    used[i] = False
                    
        backtrack([], [False] * n)
        return len(res)

Complexity

• Time: O(n! / (n-k)!) which is O(n³) for k=3.
• Space: O(n) for recursion stack and O(1) for result storage.
• Notes: More flexible than brute force if the problem length (k) were dynamic, but slightly more overhead for fixed k=3.

Approach 3: Frequency Counting

Intuition Instead of generating numbers from the input, we can iterate through all possible 3-digit even numbers (100 to 998) and check if the input digits array contains the necessary digits to form that number. This is efficient because the search space (450 numbers) is small.

Steps

• Count the frequency of each digit in the input digits array using a frequency array or hash map.
• Initialize a counter to 0.
• Iterate through all even numbers from 100 to 998 (step 2).
• For each candidate number, extract its hundreds, tens, and units digits.
• Check if the frequency map has enough of each digit to form the number (handling duplicates correctly).
• If valid, increment the counter.

from collections import Counter

class Solution:
    def findEvenNumbers(self, digits: list[int]) -> int:
        count = Counter(digits)
        res = 0
        
        for num in range(100, 1000, 2):
            temp_count = Counter([int(c) for c in str(num)])
            valid = True
            for d, c in temp_count.items():
                if count.get(d, 0) < c:
                    valid = False
                    break
            if valid:
                res += 1
                
        return res

Complexity

• Time: O(1) because we iterate through a constant range of 450 numbers and perform constant work (3 digits) for each.
• Space: O(1) for the frequency array.
• Notes: Very efficient time complexity, but requires iterating over the solution space rather than the input space.