Finding 3-Digit Even Numbers

1
2
3
4
5
6
7
8
9

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        res, cnt = [], Counter(digits)
        for i in range(1, 10):
            for j in range(0, 10):
                for k in range(0, 10, 2):
                    if cnt[i] > 0 and cnt[j] > (i == j) and cnt[k] > (k == i) + (k == j):
                        res.append(i * 100 + j * 10 + k)
        return res

The method takes as input a list of digits (from 0 to 9) and returns all the three-digit numbers that can be formed from these digits where the last digit is even.

Three Cycles

Let’s break down the code:

  1. The method begins by initializing an empty list res to hold the result, and a Counter object cnt from the collections module to count the frequency of each digit in the input list.

  2. It then runs three nested loops over the digits 1 through 9 (i), 0 through 9 (j), and 0 through 9 in steps of 2 (k). Here, i, j, and k represent the hundreds, tens, and units place of the three-digit number respectively. The last loop goes in steps of 2 to ensure that the last digit is even.

  3. Inside the loops, it checks whether the count of each digit i, j, and k in cnt is more than 0 and whether they exceed the specified conditions. This is to ensure that there are enough of each digit to form a three-digit number without using a digit more times than it appears in the input list.

  4. If the condition is satisfied, it calculates the three-digit number using the expression i * 100 + j * 10 + k, appends it to res, and continues to the next iteration.

  5. Finally, the method returns the list res, which contains all the three-digit numbers that can be formed from the input digits with an even last digit.

The complexity of this method is O(n), where n is the number of elements in the input list, because it needs to go through each element to count its frequency. The nested loops always iterate a constant number of times, so they do not depend on the size of the input.

Q&A

how do you come up with that compact solutions ?

  1. Understanding the Problem: The problem requires us to form all possible three-digit numbers from a given list of digits, where the last digit is even. This involves permutations of digits, as well as a condition that the last digit should be even.

  2. Break Down the Problem: We can divide this problem into smaller tasks:

    • Count the frequency of each digit in the list.
    • Generate all three-digit numbers.
    • Ensure the last digit is even.

  3. Draw from Past Experience: If you’ve solved problems involving permutations or combinations before, or used the Counter class from the collections module, this problem might seem familiar. The solution involves looping through possible digit values and checking if enough of each digit is available.

  4. Use Data Structures and Algorithms: The Counter class is used to count the frequency of each digit in the list. This provides an easy way to check if a digit can be used. The main algorithm involves three nested loops to generate the hundreds, tens, and units places of the numbers.

  5. Optimize: The solution is already quite efficient with a time complexity of O(n). However, if the input list is sorted and has no duplicates, we could potentially use a more efficient algorithm to generate the permutations.

  6. Iterative Approach: This problem might not be solved optimally in the first attempt. For example, you might initially forget to ensure that the last digit is even, or you might not consider the case where the same digit appears multiple times in the list. By iteratively refining your solution, you can arrive at the current optimized solution.

By following this process, you can arrive at an elegant and efficient solution like the one provided. Remember that these steps are iterative and you may need to cycle through them multiple times to arrive at the final solution.