Teaching Kids Programming – Breadth First Search Algorithm to Find Factor Combinations

Teaching Kids Programming: Videos on Data Structures and Algorithms

Numbers can be regarded as the product of their factors. For example, 8 = 2 x 2 x 2 = 2 x 4. Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n – 1].

Example 1:
Input: n = 1
Output: []

Example 2:
Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]

Example 3:
Input: n = 37
Output: []

Constraints:
1 <= n <= 10^7

Factor Combination Algorithms

• Teaching Kids Programming – Backtracking Algorithm to Find Factor Combinations (Math, Recursive Depth First Search)
• Algorithms to Compute the Factor Combinations for an Integer using DFS and BFS

Breadth First Search Algorithm to Find Factor Combinations

Similar to Backtracking (Recursive Depth First Search Algorithm with Optimizations i.e. branches pruning), we need to store a tuple that contains the current integer value, the last used factor, and the current list of factors in the search node.

In Breadth First Search Algorithm, we use a queue (deque in Python) to expand the nodes in the level by level order.

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

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
 
        q = deque([(n, 2, [])])
        while q:
            num, last, cur = q.popleft()
            for i in range(last, int(num**0.5) + 1):
                if num % i == 0:
                    ans.append(cur[:] + [i, num//i])
                    q.append((num//i, i, cur + [i]))
        
        return ans

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []

        q = deque([(n, 2, [])])
        while q:
            num, last, cur = q.popleft()
            for i in range(last, int(num**0.5) + 1):
                if num % i == 0:
                    ans.append(cur[:] + [i, num//i])
                    q.append((num//i, i, cur + [i]))
        
        return ans

The next factors to check should be no less than the last used factor, and we just have to check the possible factors up to the square root of the number – which is the same as checking a number if it is a prime.

Factor Combination Algorithms

• Teaching Kids Programming – Breadth First Search Algorithm to Find Factor Combinations
• Teaching Kids Programming – Backtracking Algorithm to Find Factor Combinations (Math, Recursive Depth First Search)
• Algorithms to Compute the Factor Combinations for an Integer using DFS and BFS

–EOF (The Ultimate Computing & Technology Blog) —