2094. Finding 3-Digit Even Numbers

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:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

  1for 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.

  1t = []
  2k = i
  3while k:
  4    t.append(k % 10)
  5    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.

  1if 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.

  1ans.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.

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:

1. 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.

2. 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.

3. 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}.

4. 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.

5. 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.

6. 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.

7. 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).

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

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:

1. The outer loop runs from 100 to 998 in steps of 2 (inclusive), which gives us 450 iterations because ((998 - 100) / 2) + 1 = 450.

2. 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.

3. 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:

1. 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).

2. A temporary list t to store the digits of the current number i, which always contains 3 digits, hence O(1).

3. 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).

4. 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.