#2094

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Finding 3-Digit Even Numbers

Generate unique 3-digit even numbers from a given array of digits with duplicates.

Problem Statement

You are given an integer array digits, where each element is a digit. The array may contain duplicates. You need to find all the unique 3-digit integers that can be formed using the digits. Only even integers are valid, and leading zeros should be avoided.

For example, if the given digits are [1, 2, 3], you can form valid integers like 132 and 312. The task is to generate all such valid even numbers from the digits, considering all combinations and avoiding duplicates. The result should include only 3-digit even numbers.

Examples

Example 1

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

Output: [102,120,130,132,210,230,302,310,312,320]

All the possible integers that follow the requirements are in the output array. Notice that there are no odd integers or integers with leading zeros.

Example 2

Input: digits = [2,2,8,8,2]

Output: [222,228,282,288,822,828,882]

The same digit can be used as many times as it appears in digits. In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3

Input: digits = [3,7,5]

Output: []

No even integers can be formed using the given digits.

Constraints

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

Solution Approach

Array Scanning

First, scan the input digits array to generate all possible combinations of three digits. Ensure each combination respects the 3-digit number requirement and is valid even (i.e., the last digit is even).

Hash Lookup for Uniqueness

Use a hash set to ensure that only unique numbers are included in the output. By adding the valid 3-digit even numbers to the set, you automatically handle duplicates.

Handling Leading Zeros

While forming the combinations, make sure that no number has a leading zero, as this would invalidate the number (e.g., 012 is not a valid number).

Complexity Analysis

Metric	Value
Time	O(k \cdot 10^k)
Space	O(1)

The time complexity is O(k * 10^k), where k is the number of digits, as we generate all possible combinations. The space complexity is O(1) as we use a constant amount of space for storing the results after processing the combinations.

What Interviewers Usually Probe

Checks understanding of array scanning for combinations.
Evaluates use of hash sets for uniqueness and performance.
Assesses handling of edge cases like leading zeros and no even numbers.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle leading zeros, which would result in invalid numbers.
Not using a hash set to store unique numbers, leading to repeated numbers in the result.
Overlooking the constraint that only even numbers should be generated.

Follow-up variants

Using larger arrays with more digits.
Ensuring the solution works with arrays containing only odd digits.
Optimizing the algorithm to handle larger inputs more efficiently.

FAQ

What is the pattern used to solve the 'Finding 3-Digit Even Numbers' problem?

The problem follows a pattern of array scanning plus hash lookup to generate unique valid 3-digit even numbers.

How do I handle duplicates in the 'Finding 3-Digit Even Numbers' problem?

You can handle duplicates by using a hash set to store only unique combinations of valid 3-digit even numbers.

What should I do if the array contains leading zeros?

Make sure to avoid leading zeros when forming numbers by checking the first digit of each combination before adding it to the result.

Can I solve the 'Finding 3-Digit Even Numbers' problem without checking for even numbers?

No, the problem requires that all generated numbers must be even, so the last digit must be even for each valid combination.

What is the time complexity of the 'Finding 3-Digit Even Numbers' problem?

The time complexity is O(k * 10^k), where k is the number of digits, because you generate combinations and check each one for validity.

terminal

Solution

Solution 1: Counting + Enumeration

First, we count the occurrence of each digit in $\textit{digits}$, recording it in an array or hash table $\textit{cnt}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        cnt = Counter(digits)
        ans = []
        for x in range(100, 1000, 2):
            cnt1 = Counter()
            y = x
            while y:
                y, v = divmod(y, 10)
                cnt1[v] += 1
            if all(cnt[i] >= cnt1[i] for i in range(10)):
                ans.append(x)
        return ans

Continue Practicing

#2122 recover the original array #2099 find subsequence of length k with the largest sum #2135 count words obtained after adding a letter