2094. Finding 3-Digit Even Numbers

EasyArrayHash TableEnumerationSorting

Problem Description

The LeetCode problem entails finding all unique integers that can be formed by concatenating three distinct elements from a given array digits. The resulting integers must meet the following criteria: they should not start with a zero, they should be even, and they can be created from any combination of three elements from the given digits. The unique integers found must then be arranged in ascending order.

A bit more detailed description of the requirements is as follows:

Three-element Concatenation: When we talk about concatenation, we're referring to joining the elements together in sequence. In the context of this problem, we are joining three digits to make a new integer.
No Leading Zeros: The integers that are formed should not have a zero as the first digit, because this would make the integer a two-digit or one-digit number rather than a three-digit one.
Integers Must Be Even: The integers formed after concatenation have to be even. A number is even when it ends with 0, 2, 4, 6, or 8.
Must Use Digits From the Array: The integers must be constructed from the digits provided in the input array digits.
The Result Should Be Unique: If there are duplicate digits in the given array, they can only be used as many times as they appear in the array, and the resulting integers should be unique (no repeating integers).

The question requires finding all such possible unique integers and returning them as a sorted list.

Intuition

To solve this problem, a brute-force method can be applied—we can attempt to construct three-digit even numbers starting from the smallest (100 since we cannot have leading zeros) to the largest possible (998 because it is the largest three-digit even number) and check if each number can be formed using the given digits. This approach systematically checks each number within the specified range, thus guaranteeing we don't miss any possible solutions.

Here are the steps that we take to arrive at the solution:

Form a Counter: First, count the occurrences of each digit in the input digits array using a Counter. This is done so we can keep track of how many times we can use each digit from digits.
Iterate Over Even Numbers: We then iterate over every even number from 100 to 998 (inclusive). We only look at even numbers because that's one of the constraints given.
Check if Number Can Be Constructed: For each number, we break it down into its individual digits and count the occurrences using another Counter. We then compare this counter with the one we acquired from the digits array to check if we have enough of each digit to construct the current number.
Store Valid Numbers: If all digits from the number can be formed using the digits we have, we add the number to the answer list.
Return Sorted List: After checking all numbers, the ans list will contain all the unique integers meeting the requirements. The list will inherently be sorted since we iterated through the numbers in ascending order.

Learn more about Sorting patterns.

Solution Approach

The implementation of the provided solution utilizes a Counter from the collections module, which is a subclass of a dictionary that is used to count hashable objects. In this case, it's used to count the occurrences of each digit in both the digits array and the numbers we're trying to construct.

Here's how the implementation works, step by step:

Initializing the Answer List: An empty list called ans is created to store all valid numbers that meet the criteria.
Create a Counter for the Input Digits: A Counter object is instantiated with the input digits array. This provides a count of each digit available to us for constructing numbers.
Iterate through the Range of Numbers: A for-loop is used to iterate through the range of possible three-digit even integers starting from 100 to 999. The step is 2 because only even numbers need to be considered.
```
for i in range(100, 1000, 2):
```
Breaking Down Numbers and Counting Digits: Inside the loop, each number is broken down into its constituent digits. This is done by repeatedly taking the modulus of 10 and dividing the number by 10 until the number is reduced to zero.
```
t = []
k = i
while k:
    t.append(k % 10)
    k //= 10
```
Create a Counter for the Current Number: A Counter object is then created for the current number's digits.
Validity Check: Using list comprehension, a check is performed to see if the count of each digit needed to construct the current number is less than or equal to the count of that digit in the input digits. This uses the all built-in function to ensure all digits are sufficiently available.
```
if all([counter[i] >= cnt[i] for i in range(10)]):
```
Adding to the Answer List: If the current number is valid (it can be built from the available digits), it is appended to the ans list.
```
ans.append(i)
```
Return the Result: The ans list is already sorted since the iteration is in ascending order. Thus, the final list is returned as the answer.

This algorithm effectively goes through each three-digit even number and tries constructing it from the digits. It's worth noting that this brute-force method is not the most optimal in terms of time complexity. However, since the range of numbers we're looking at is small (just 450 in total, from 100 to 998 every even number), it's acceptable here. A more efficient algorithm would use backtracking or permutation generation to avoid unnecessary checks, especially for larger ranges.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Suppose we are given an input array digits of [1, 2, 0, 3]. Our goal is to construct all unique three-digit even numbers that could be formed from these digits without leading zeros. Here's how we'll proceed:

Form a Counter: We first count the occurrences of each digit in digits, resulting in a counter like this: {1:1, 2:1, 0:1, 3:1}. This tells us we have each digit once.
Iterate Over Even Numbers: Now, we start iterating over every even number from 100 to 998. We will test 102, as it's the next even number after 100.
Check if Number Can Be Constructed: To check if 102 can be formed, we decompose it into its constituent digits [1, 0, 2]. Then we form a counter for these digits: {1:1, 0:1, 2:1}.
Store Valid Numbers: We compare this counter with our digit counter from step 1. Since they match, 102 can be constructed with our digits. 102 gets added to our answer list.
Skipping Invalid Numbers: Next, we would test 104 for instance, but we can skip this because we do not have two occurrences of the digit 1. Therefore, 104 cannot be formed and is not added to our list.
Skip Leading Zero: If we had a number that started with a zero, say 204, we would have skipped it because we can't have a number with leading zeros.
Even Number Consideration: We continue our process, but upon trying to form 103, we discard it since it's not an even number (it doesn't end with 0, 2, 4, 6, or 8).
Return Sorted List: Continuing this process for the whole range from 100 to 998, we finally construct the list of all valid numbers. For this example, let's say our complete list of valid numbers is [102, 120, 130, 132, 210, 230, 302, 310, 312, 320].

This list is then returned as the sorted list of all unique three-digit even numbers that can be created from the given digits.

By following these steps, we systematically explore all possible three-digit even numbers and validate whether they can be constructed with the provided digits, ensuring we include only the unique and valid ones in our final sorted list.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def findEvenNumbers(self, digits: List[int]) -> List[int]:
6        # Initialize a list to hold the resulting even numbers
7        even_numbers = []
8      
9        # Create a counter for the digits to keep track of their occurrences
10        digit_count = Counter(digits)
11      
12        # Iterate through all three-digit even numbers
13        for num in range(100, 1000, 2):
14            temp = []  # temporary list to hold the digits of the current number
15            current_number = num
16            # Extract digits from the current number
17            while current_number:
18                temp.append(current_number % 10)
19                current_number //= 10
20          
21            # Create a counter for the extracted digits
22            temp_count = Counter(temp)
23          
24            # Compare our digit_count with temp_count to ensure we can construct the number with given digits
25            if all(digit_count[digit] >= temp_count[digit] for digit in range(10)):
26                even_numbers.append(num)  # If we can, add the number to our even_numbers list
27      
28        # Return the list of constructed even numbers
29        return even_numbers
30

1class Solution {
2    public int[] findEvenNumbers(int[] digits) {
3        // Count the occurrences of each digit
4        int[] digitCount = countDigitOccurrences(digits);
5        List<Integer> evenNumbers = new ArrayList<>();
6      
7        // Iterate over even 3-digit numbers
8        for (int num = 100; num < 1000; num += 2) {
9            // Get the counts for the current number
10            int[] currentDigitCount = getDigitCount(num);
11            // Check if the number can be made from given digits
12            if (canMakeNumber(digitCount, currentDigitCount)) {
13                // Add number to the results list
14                evenNumbers.add(num);
15            }
16        }
17      
18        // Convert List<Integer> to int[]
19        return evenNumbers.stream().mapToInt(Integer::intValue).toArray();
20    }
21
22    /**
23     * Checks if a number's digits can be constructed from the available digit counts.
24     */
25    private boolean canMakeNumber(int[] availableCount, int[] requiredCount) {
26        for (int i = 0; i < 10; i++) {
27            // If the required count for a digit exceeds the available count, return false
28            if (availableCount[i] < requiredCount[i]) {
29                return false;
30            }
31        }
32        // If all required digits are available, return true
33        return true;
34    }
35
36    /**
37     * Count the occurrences of each digit in the given array.
38     */
39    private int[] countDigitOccurrences(int[] nums) {
40        int[] counter = new int[10];
41        for (int num : nums) {
42            counter[num]++;
43        }
44        return counter;
45    }
46
47    /**
48     * Returns an array representing the count of each digit in the given number.
49     */
50    private int[] getDigitCount(int num) {
51        int[] count = new int[10];
52        // Split the number into its digits and count each occurrence
53        for (; num > 0; num /= 10) {
54            int digit = num % 10;
55            count[digit]++;
56        }
57        return count;
58    }
59}
60

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to find all unique three-digit even numbers that can be formed 
7    // by the given digits where each digit from the array can be used at most once.
8    vector<int> findEvenNumbers(vector<int>& digits) {
9        vector<int> digitCount = countDigits(digits); // Count the frequency of each digit in the input vector
10        vector<int> evenNumbers; // Will hold all the valid even numbers
11
12        // Loop through all even numbers between 100 and 999.
13        // We start at 100 because we need a three-digit number, and it has to be even.
14        for (int num = 100; num < 1000; num += 2) {
15            vector<int> numDigits = getDigits(num); // Split the number into its individual digits
16            vector<int> numDigitCount = countDigits(numDigits); // Count the frequency of each digit
17          
18            // Check if the number can be formed using the given digits
19            if (canFormNumber(digitCount, numDigitCount)) {
20                evenNumbers.push_back(num); // Add the number to the results
21            }
22        }
23        return evenNumbers; // Return the list of valid three-digit even numbers
24    }
25
26    // Helper function to count the frequency of each digit in a vector
27    vector<int> countDigits(vector<int>& nums) {
28        vector<int> counter(10, 0); // Initialize a vector of 10 zeros for digits 0-9
29        for (int num : nums) {
30            counter[num]++; // Increment the count for each digit encountered
31        }
32        return counter; // Return the vector of digit frequencies
33    }
34
35    // Helper function to check if a number can be formed with the given digits
36    bool canFormNumber(vector<int>& availableDigits, vector<int>& neededDigits) {
37        for (int i = 0; i < 10; ++i) {
38            if (availableDigits[i] < neededDigits[i]) {
39                // If there are not enough of a digit to form the number, return false
40                return false;
41            }
42        }
43        return true; // If all digits are available, return true
44    }
45
46    // Function to decompose a number into its individual digits
47    vector<int> getDigits(int num) {
48        vector<int> digits;
49        while (num > 0) {
50            digits.push_back(num % 10); // Extract the last digit
51            num /= 10; // Remove the last digit from the number
52        }
53        reverse(digits.begin(), digits.end()); // Reverse the vector to get the correct digit order
54        return digits;
55    }
56};
57

1// This function generates all possible non-repeating three-digit even numbers
2// using the digits provided in the input array 'digits'.
3function findEvenNumbers(digits: number[]): number[] {
4    // Initialize a record array to count the occurrences of each digit (0-9) in the input array.
5    let digitCounter = new Array(10).fill(0);
6    for (let digit of digits) {
7        digitCounter[digit]++;
8    }
9
10    let result: number[] = [];
11    // Iterate from 100 to 999 to generate all possible three-digit even numbers.
12    for (let i = 100; i < 1000; i += 2) {
13        // Convert the current number to a string to work with each digit individually.
14        if (isConstructible(digitCounter, String(i))) {
15            // If the number is constructible from the input digits, add it to the result array.
16            result.push(i);
17        }
18    }
19    return result;
20}
21
22// This helper function checks if a three-digit number, represented as a string 'digits',
23// can be constructed from the digit occurrences recorded in 'targetCounter'.
24function isConstructible(targetCounter: Array<number>, digits: string): boolean {
25    // Initialize a local record array to count the occurrences of each digit in 'digits'.
26    let localCounter = new Array(10).fill(0);
27    for (let digit of digits) {
28        localCounter[parseInt(digit)]++;
29    }
30
31    for (let i = 0; i < 10; i++) {
32        // If the local counter for any digit exceeds that in the target counter,
33        // the number cannot be constructed and the function returns false.
34        if (localCounter[i] > targetCounter[i]) return false;
35    }
36  
37    // If the function hasn't already returned false, it means the number can be constructed,
38    // so return true.
39    return true;
40}
41

Time and Space Complexity

Time Complexity

The given code snippet generates all even three-digit numbers (from 100 to 998) and checks whether each number can be formed by the digits available in the digits list. The time complexity is determined by the following factors:

The outer loop runs from 100 to 998 in steps of 2 (inclusive), which gives us 450 iterations because ((998 - 100) / 2) + 1 = 450.
For each iteration, it performs the conversion of the number i into its digits and checks against the count of available digits. This operation is constant time for three-digit numbers since the division and modulo operations happen exactly three times per number.
The all function inside the loop checks if all digits of the current number are available in the sufficient quantity. It does so by iterating over all possible digits 0 to 9, resulting in up to 10 iterations.

Combining these points, the number of constant-time operations performed in the loop is 450 * 3 * 10, giving us a time complexity of O(1) regardless of the input size (since we are only considering three-digit even numbers and the number of digits in the English numerical system is constant).

Space Complexity

The space complexity of the given code involves the following considerations:

The counter for the input digits, which has a space complexity proportional to the number of unique digits in digits, which is at most 10. Therefore, it is O(1).
A temporary list t to store the digits of the current number i, which always contains 3 digits, hence O(1).
A temporary Counter object cnt for the currently considered number i. Since it will always have at most 3 entries (for the three digits), it is also O(1).
The answer list ans that stores the resulting numbers. In the worst case, ans could store up to 450 three-digit even numbers, which is the total count of even numbers between 100 and 998. Thus this is O(1) as well.

Given these considerations, the space complexity of the code is O(1) since all space-consuming objects have a fixed upper bound irrespective of the input size.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know