How should I practice Factor Combinations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related LinkedIn phone screen problems in FastPrep.

Is Factor Combinations associated with LinkedIn?

FastPrep tags this as a LinkedIn phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Backtracking

Factor Combinations

Learn this problem

● Medium

LinkedInINTERNPHONE SCREEN

Problem statement

Given an integer n, return every unique combination of integers greater than 1 whose product is n.

Do not include the one-element combination [n]. Within each combination, factors must be in nondecreasing order. Return all combinations in lexicographic order so that the output is deterministic.

Function

getFactors(n: int) → int[][]

Examples

Example 1

n = 12return = [[2,2,3],[2,6],[3,4]]

The three nontrivial nondecreasing factorizations of 12 are 2 * 2 * 3, 2 * 6, and 3 * 4.

Example 2

n = 16return = [[2,2,2,2],[2,2,4],[2,8],[4,4]]

Nondecreasing order removes permutations such as [8, 2].

Example 3

n = 37return = []

37 is prime, so it has no nontrivial factor combination.

Constraints

2 <= n <= 10000000
Every returned factor is greater than 1 and less than n.
The total number of valid combinations fits comfortably in memory.