Coding

Factor Combinations

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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].

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

Find valid factorizations using numbers in [2, 11]:

12 = 2 × 6
12 = 3 × 4
12 = 2 × 2 × 3 These are all valid factorizations, so they are included in the output.

Input: n = 1 Output: [] Explanation: Factors must be in the range [2, n-1], but 1 has no valid factors in this range. No possible factorization → Output is empty.

Input: n = 8

1 <= n <= 107

cpp

class Solution {
    vector<vector<int>> getFactors(int n) {
        // Your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> getFactors(int n) {
        // Your code goes here
    }
}

python

class Solution(object):
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        # Your code goes here

javascript

/**
 * @param {number} n
 * @return {number[][]}
 */
var getFactors = function(n) {
    // Your code goes here
};

csharp

public class Solution
{
    public IList<IList<int>> GetFactors(int n)
    {
        // Your code goes here
    }
}

func getFactors(n int) [][]int {} {

Stuck? Show a way to structure it+

01DFS on the remaining quotient with a minimum allowed factor.
02Try divisors from that minimum through sqrt(remaining).
03For each divisor, append it and recurse on the quotient.
04Add the final quotient as the last factor when it respects ordering.

Reference answer

Generate factorizations with DFS (remaining, start, path). Try every divisor d from start through sqrt(remaining) that divides remaining. Append d, recurse on remaining/d with the same d as the new minimum, then backtrack. At each such choice, append the complementary quotient to form a complete combination. Requiring nondecreasing factors ensures [2,6] is generated but [6,2] is not. Do not include the trivial single factor n; factors must be in [2,n-1]. Runtime is output-sensitive, with divisor checks bounded by square roots along the search.

Complexity: Enumerating factor combinations requires O(sqrt(n) + output) search work in the usual divisor DFS, with O(log n) recursion space excluding returned combinations.

Then expect these follow-ups

How would you count combinations without listing them?
Tests: combinatorial search
How would prime factorization help prune candidates?
Tests: number theory

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question