627. Factor Combinations
A warehouse stores n identical crates and wants to stack them in a rectangular block with several layers: a stacking plan splits the crates as a product of two or more whole numbers, each at least 2, such as 2 x 3 x 5 for n = 30. The plan n on its own (a single factor) is not allowed. Plans that use the same numbers in a different order count as one plan.
Return every different plan as an array of its factors. The plans may be returned in any order and the factors inside a plan may be in any order.
Example 1
- Input:
- n = 12
- Output:
- [[2,6],[2,2,3],[3,4]]
- Explanation:
Three plans exist:
[2, 6],[3, 4]and[2, 2, 3].
Example 2
- Input:
- n = 13
- Output:
- []
- Explanation:
13 is prime, so it cannot be split into factors of at least 2: the answer is empty.
Example 3
- Input:
- n = 36
- Output:
- [[2,18],[2,2,9],[2,2,3,3],[2,3,6],[3,12],[3,3,4],[4,9],[6,6]]
- Explanation:
Plans for 36 include
[2, 18],[6, 6],[3, 3, 4]and[2, 2, 3, 3]; there are eight in total.
Constraints
- 2 ≤
n≤ 5000
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(answer size * log n)
- Space
- O(log n)