Solution: Factor Combinations

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Factor Combinations

Table of Contents

Contents are not accessible

Problem Statement

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.

Example 1:

Input: n = 8  
Output: [[2, 2, 2], [2, 4]]

Example 2:

Input: n = 20  
Output: [[2, 2, 5], [2, 10], [4, 5]]

Constraints:

2 <= n <= 10<sup>7</sup>

Solution

We can use backtracking to find all the factors of a given number $n$ .

We will start by iterating through all integers from start (2 by default) to the square root of $n + 1$ . If the current integer i divides n, we will add i to the list of current factors curr and appends this list along with the corresponding factor of $n/i$ to the list of all factors (result). Then we can recursively call the function with $n / i$ as the new input, i as the new start value, and curr and result as the current factors and results. After each recursive call, we have to pop the last element from curr to backtrack and find other factors.

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

We can't have more than $O(n)$ factors of a number n. This means that getAllFactors can be called a maximum of $O(n)$ times recursively. The for loop iterates a maximum of $O(sqrt(n))$ . This means that the overall time complexity is $O(n * sqrt(n))$ or $(n^{1.5})$

Space Complexity

Ignoring the space needed for the output array, the space complexity will be $O(log(n))$ as we need to save only one factor while in the recursion, and our recursion tree won't get bigger than $O(log(n))$ steps.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible