LeetCode 3483 - Unique 3-Digit Even Numbers

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Recursion, Enumeration

Solution

Here’s a comprehensive technical guide for LeetCode 3483 following your requested format:

Problem Understanding

The problem asks us to determine the number of distinct three-digit even numbers that can be formed from an array of digits called digits. Each digit in the array can only be used once per number, but the array may contain duplicates, allowing repeated digits to be used across different numbers as long as the copies exist. Importantly, numbers cannot have leading zeros, so any number starting with 0 is invalid.

The input is a list of integers between 0 and 9, and the length of this list is between 3 and 10. This constraint ensures that the input is small enough to consider combinatorial solutions but large enough that a purely brute-force solution that checks every 3-digit permutation without optimizations could be less efficient.

Edge cases include arrays with all odd numbers (produces zero results), arrays where some digits are duplicated (affects the number of distinct combinations), arrays containing zeros (must be avoided in the hundreds place), and arrays where all digits are the same (only one valid number if even).

Approaches

Brute Force

The brute-force approach generates all possible 3-digit permutations of the given digits. For each permutation, it checks if the number is even (last digit is even) and if the first digit is not zero. Using a set ensures only distinct numbers are counted. This approach is correct because it explicitly considers all valid combinations. However, it is less efficient because the number of permutations grows factorially with the number of digits (O(n^3) here since we only take 3-length permutations), and repeatedly generating numbers and checking them is redundant for larger inputs.

Optimal Approach

The key insight for optimization is that a three-digit number has three positions: hundreds, tens, and units. We can iterate through these positions systematically using a frequency array or counter to avoid generating invalid numbers or duplicates unnecessarily. Specifically:

The hundreds digit cannot be 0.
The units digit must be even.
The tens digit can be any remaining digit.

By counting the occurrences of each digit, we can use nested loops over possible hundreds, tens, and units digits while decrementing the count temporarily to ensure a digit is only used once per number. This avoids generating permutations that violate constraints, and using a set ensures uniqueness. This method is more efficient because it only considers valid candidate numbers.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n^3)	Generate all 3-digit permutations and filter valid numbers
Optimal	O(n^3)	O(1)	Iterate over digit positions with counting, avoids invalid numbers early, uses set for uniqueness

Although both approaches are technically O(n^3) in the worst case (with n ≤ 10), the optimal approach avoids unnecessary computations and scales better for duplicates or invalid digits.

Algorithm Walkthrough

Count the frequency of each digit in the array. This allows quick checks of whether a digit can be used in a position without exceeding its availability.
Initialize a set to store distinct valid numbers.
Iterate through all digits for the hundreds place. Skip 0 because numbers cannot start with zero.
For each chosen hundreds digit, iterate through all digits for the tens place. Skip the digit if it was already used in hundreds, respecting frequency constraints.
For each hundreds-tens combination, iterate through all digits for the units place. Only consider even digits and ensure the digit has not been used more times than it appears in the input.
Combine the hundreds, tens, and units digits to form a number. Add it to the set.
After iterating through all valid combinations, return the size of the set.

Why it works: By iterating systematically through hundreds, tens, and units digits while respecting the frequency constraints and the rules for valid numbers (no leading zero, even last digit), we ensure all possible valid numbers are counted exactly once. The set guarantees uniqueness.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        freq = Counter(digits)
        unique_numbers = set()
        
        for h in range(1, 10):
            if freq[h] == 0:
                continue
            freq[h] -= 1
            for t in range(0, 10):
                if freq[t] == 0:
                    continue
                freq[t] -= 1
                for u in [0, 2, 4, 6, 8]:
                    if freq[u] == 0:
                        continue
                    unique_numbers.add(h * 100 + t * 10 + u)
                freq[t] += 1
            freq[h] += 1
        
        return len(unique_numbers)

This Python code first counts the digit frequencies, then iterates through hundreds, tens, and valid units digits. The frequency map ensures digits are not reused beyond availability. A set keeps only distinct numbers.

Go Solution

func totalNumbers(digits []int) int {
    freq := make([]int, 10)
    for _, d := range digits {
        freq[d]++
    }

    uniqueNumbers := make(map[int]struct{})

    for h := 1; h <= 9; h++ {
        if freq[h] == 0 {
            continue
        }
        freq[h]--
        for t := 0; t <= 9; t++ {
            if freq[t] == 0 {
                continue
            }
            freq[t]--
            for _, u := range []int{0, 2, 4, 6, 8} {
                if freq[u] == 0 {
                    continue
                }
                num := h*100 + t*10 + u
                uniqueNumbers[num] = struct{}{}
            }
            freq[t]++
        }
        freq[h]++
    }

    return len(uniqueNumbers)
}

In Go, a map is used to store distinct numbers. Slices are iterated instead of lists. The approach mirrors Python closely, respecting frequencies and valid digit rules.

Worked Examples

Example 1: `digits = [1,2,3,4]`

Frequencies: {1:1, 2:1, 3:1, 4:1}
Hundreds digit options: 1, 2, 3, 4
Tens digit options: any remaining digit
Units digit options: 2, 4 (even digits)
Unique numbers generated: 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, 432
Return count: 12

Example 2: `digits = [0,2,2]`

Frequencies: {0:1, 2:2}
Hundreds: only 2 (cannot be 0)
Tens: 0 or 2 (but only one 2 used already)
Units: 0 or 2 (even digits, respecting frequency)
Unique numbers: 202, 220
Return count: 2

Example 3: `digits = [6,6,6]`

Frequencies: {6:3}
Hundreds: 6, Tens: 6, Units: 6
Unique number: 666
Return count: 1

Example 4: `digits = [1,3,5]`

No even digits for units
Return count: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^3)	Three nested loops over at most 10 digits each
Space	O(n)	Frequency counter and set of unique numbers

The time complexity is cubic in the number of digits (n ≤ 10), which is acceptable. Space is linear due to the small counter and set.

Test Cases

# Basic provided examples
assert Solution().totalNumbers([1,2,3,4]) == 12  # mix of digits
assert Solution().totalNumbers([0,2,2]) == 2     # includes zero
assert Solution().totalNumbers([6,6,6]) == 1     # all same even digits
assert Solution().totalNumbers([1,3,5]) == 0     # no even digits

# Boundary and edge cases
assert Solution().totalNumbers([0,0,0,2]) == 1   # zero-heavy
assert Solution().totalNumbers([0,1,2,2,4,6,8]) == 36 # larger array
assert Solution().totalNumbers([2,4,6,8]) == 24  # all even, no zeros
assert Solution().totalNumbers([0,1,2]) == 1     # smallest valid array with zero

Test	Why
[1,2,3,4]	Standard input, all digits usable
[0,2,2]	Tests zero in the array and repeated digits
[6,6,6]	All digits identical, ensures correct counting
[1,3,5]	No valid number, edge case
[0,0,0,2]	Tests handling multiple zeros
[0,1,2,2,4,6,8]	Larger input