Teaching Kids Programming – Finding 3-Digit Even Numbers (Permutations, Brute Force)

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 (Permutations, Brute Force)

The 3-digit numbers are limited, from 100, 102, 104 to 996, 998. We can bruteforce these 3 digit numbers to see if they can be made from the given digits. We don’t need to sort the answer since the numbers are checked in the sorted order. To check if the 3-digit number can be made from the given digits, we can compare two Counter object. The following time complexity is O(N) i.e. the Counter(digits) takes O(N) time where N is the length of the digit array. And it follows by a constant loop.

1
2
3
4
5
6
7
8

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        x = Counter(digits)
        ans = []
        for i in range(100, 1000, 2):            
            if Counter((i // 100, (i // 10) % 10, i % 10)) <= x:
                ans.append(i)
        return ans

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        x = Counter(digits)
        ans = []
        for i in range(100, 1000, 2):            
            if Counter((i // 100, (i // 10) % 10, i % 10)) <= x:
                ans.append(i)
        return ans

Another slightly different implementation is as follows, where we have 3 nested loops one for each digit, with O(1) time complexity.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = []
        c = Counter(digits)
        for x in range(1, 10):            
            for y in range(10):
                for z in range(0, 10, 2):
                    if Counter((x, y, z)) <= c:
                        ans.append(x * 100 + y * 10 + z)
        return ans

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = []
        c = Counter(digits)
        for x in range(1, 10):            
            for y in range(10):
                for z in range(0, 10, 2):
                    if Counter((x, y, z)) <= c:
                        ans.append(x * 100 + y * 10 + z)
        return ans

We can also bruteforce the permutations which is P(N, 3) – picking three out of N. We can have 3 nested loops, one for the index of each digit. The time complexity is O(N^3+MLogM) where N is the given length of the digits, and M is the length of the output, which in worst case, M=P(N, 3)=N^3. Indices cannot be re-picked, and thus we have to continue/skip in the loops when the current picked index is taken already.

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

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = set()
        c = Counter(digits)
        n = len(digits)
        for x in range(n):
            for y in range(n):
                if x == y:
                    continue
                for z in range(n):
                    if x == z or y == z:
                        continue
                    if digits[z] & 1 == 0 and digits[x] > 0 and Counter((digits[x], digits[y], digits[z])) <= c:
                        ans.add(digits[x] * 100 + digits[y] * 10 + digits[z])
        return sorted(ans)

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = set()
        c = Counter(digits)
        n = len(digits)
        for x in range(n):
            for y in range(n):
                if x == y:
                    continue
                for z in range(n):
                    if x == z or y == z:
                        continue
                    if digits[z] & 1 == 0 and digits[x] > 0 and Counter((digits[x], digits[y], digits[z])) <= c:
                        ans.add(digits[x] * 100 + digits[y] * 10 + digits[z])
        return sorted(ans)

We can also use the permutations function from functool to get the actual permutations:

1
2
3
4
5
6
7

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = set()
        for x, y, z in permutations(digits, 3):
            if x and z & 1 == 0:
                ans.add(x * 100 + y * 10 + z)
        return sorted(ans)

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        ans = set()
        for x, y, z in permutations(digits, 3):
            if x and z & 1 == 0:
                ans.add(x * 100 + y * 10 + z)
        return sorted(ans)

This in practice is faster than the above solution (3 nested loops for each index to be picked), however it has the same time/space complexity.

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