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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question