#3483

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Unique 3-Digit Even Numbers

Given an array of digits, find how many distinct 3-digit even numbers can be formed without repetition of digits and no leading zeros.

array hash table recursion enumeration

Problem Statement

You are given an array of digits, and your task is to determine how many distinct three-digit even numbers can be formed using these digits. Each digit can only be used once per number, and the number must not have leading zeros. The challenge involves both constructing valid numbers and avoiding duplication.

For example, given the input digits = [1, 2, 3, 4], the output is 12 because there are 12 distinct 3-digit even numbers that can be made, such as 124, 132, and 432. The digits must form a valid even number, so only combinations ending with an even digit are allowed.

Examples

Example 1

Input: digits = [1,2,3,4]

Output: 12

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

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

Only 666 can be formed.

Constraints

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

Solution Approach

Brute Force Enumeration

Start by generating all possible 3-digit combinations from the digits array. Ensure each digit is used only once, and check that the last digit is even to satisfy the condition of forming an even number.

Hash Set for Distinctness

To ensure uniqueness, store the formed numbers in a hash set. This will automatically eliminate any duplicate numbers formed by the same digits.

Exclusion of Leading Zeros

When forming combinations, ensure that the first digit is not zero, as leading zeros are not allowed in a valid three-digit number.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of possible 3-digit combinations. Since the digits array has at most 10 digits, the approach generates O(n^3) possibilities, where n is the length of the digits array. Space complexity is O(n^3) for storing all valid distinct combinations in a hash set.

What Interviewers Usually Probe

Check if the candidate optimizes for distinctness using hash sets.
Observe if the candidate considers leading zeros when enumerating combinations.
Look for awareness of efficient enumeration and hashing techniques to avoid unnecessary checks.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude leading zeros, which would result in invalid numbers.
Not using a hash set to eliminate duplicate numbers, leading to incorrect counts.
Overcomplicating the approach by not focusing on the problem's brute-force nature and simple constraints.

Follow-up variants

Modify the problem to allow multiple occurrences of each digit to be used in combinations.
Expand the problem to handle non-even numbers.
Alter the problem to generate n-digit even numbers instead of just three-digit ones.

FAQ

What is the key pattern in the Unique 3-Digit Even Numbers problem?

The key pattern is array scanning combined with hash lookups to ensure distinct combinations of digits forming valid 3-digit even numbers.

How can I avoid generating duplicate numbers in the solution?

Use a hash set to store the generated numbers. This ensures that only distinct numbers are counted.

What should I do if the digits array contains leading zeros?

Make sure to exclude combinations where the first digit is zero, as these are not valid 3-digit numbers.

Can I use brute force for this problem?

Yes, brute force is a suitable approach for this problem, as the constraints are small enough to explore all combinations efficiently.

How does GhostInterview help with solving this problem?

GhostInterview guides you through the solution approach, helping you avoid common pitfalls and providing suggestions for efficient implementation.

terminal

Solution

Solution 1: Hash Set + Enumeration

We use a hash set $\textit{s}$ to record all distinct three-digit even numbers, and then enumerate all possible three-digit even numbers to add them to the hash set.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        s = set()
        for i, a in enumerate(digits):
            if a & 1:
                continue
            for j, b in enumerate(digits):
                if i == j:
                    continue
                for k, c in enumerate(digits):
                    if c == 0 or k in (i, j):
                        continue
                    s.add(c * 100 + b * 10 + a)
        return len(s)

Continue Practicing

#3434 maximum frequency after subarray operation #3548 equal sum grid partition ii #3404 count special subsequences