Teaching Kids Programming – Finding 3-Digit Even Numbers (Recursive Depth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.
For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:
Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 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]
Explanation: 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: []
Explanation: No even integers can be formed using the given digits.

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

The range of possible answers includes all even numbers between 100 and 999 inclusive. Could you check each possible answer to see if it could be formed from the digits in the array?

Finding 3-Digit Even Numbers (Recursive Depth First Search Algorithm)

We can search for 3 digit permutations using the Depth First Search Algorithm, we can do this via Recursion or Iterative (with a Stack).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:        
        self.ans = set()
        freq = Counter(digits)        
        def dfs(c):
            if c >= 100:
                if c & 1 == 0:
                    self.ans.add(c)
                return
            for i in range(10):
                if freq[i] > 0:
                    freq[i] -= 1
                    dfs(c * 10 + i)
                    freq[i] += 1        
        dfs(0)
        return sorted(self.ans)        

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:        
        self.ans = set()
        freq = Counter(digits)        
        def dfs(c):
            if c >= 100:
                if c & 1 == 0:
                    self.ans.add(c)
                return
            for i in range(10):
                if freq[i] > 0:
                    freq[i] -= 1
                    dfs(c * 10 + i)
                    freq[i] += 1        
        dfs(0)
        return sorted(self.ans)        

Before the Recursive call, we need to borrow the digit (the corresponding frequency needs to be decremented), and right after the recursive call, we need to return it (give it back) by incrementing the digit’s counter. The time complexity is O(P(N, 3) + MLogM) where M is P(N, 3) and thus the overall complexity is O(MLogM) where M is P(N, 3) since the P(N, 3) single term is trivial.

The terminal case for the Recursion is that when we have 3 digits, we need to check if it is an even number, if yes, we add it to the answer (set, for unique numbers only), we stop the recursion anyway.

Finding 3-Digit Even Numbers from a Given List of Digits

• Teaching Kids Programming – Finding 3-Digit Even Numbers (Breadth First Search Algorithm)
• Teaching Kids Programming – Finding 3-Digit Even Numbers (Recursive Depth First Search Algorithm)
• Teaching Kids Programming – Finding 3-Digit Even Numbers (Permutations, Brute Force)

–EOF (The Ultimate Computing & Technology Blog) —