Leetcode: Factor Combinations

By | 2018 年 9 月 22 日

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
= 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

You may assume that n is always positive.
Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]
Example 3:

Input: 12
Output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
Example 4:

Input: 32
Output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]

Analyze

Recursively get the factors of n by checking the numbers in range from 2 to n/2. If the number is a factor of n, then recursively get the factors list of the counterpart.

Use a map from integer to factors list to speedup the process.

Solutions

Ruby

# @param {Integer} n
# @return {Integer[][]}
def get_factors(n)
@saved_factors ||= {}
return @saved_factors[n] unless @saved_factors[n].nil?

factors = []
2.upto(n/2) do |i|
if n % i == 0
j = n / i
factors << [i, j] if i <= j
factors_j = get_factors(j)
factors += factors_j.select{|fj| fj.first >= i}.map{|fj| [i] + fj}
end
end

@saved_factors[n] = factors
end

Beats 100% ruby solutions with cache:

Java

class Solution {
private Map<integer, list=""    <list<integer="">&gt;&gt; cache;</integer,>

public Solution() {
this.cache = new HashMap<integer, list=""   <list<integer="">&gt;&gt;();
}</integer,>

private List<integer> pair(int i, int j) {
List<integer> list = new ArrayList<integer>(2);
list.add(i);
list.add(j);
return list;
}</integer></integer></integer>

private List<integer> extendFactor(int i, List<integer> sourceFactors) {
List<integer> list = new ArrayList<integer>(sourceFactors.size() + 1);
list.add(i);
for(Integer j : sourceFactors) {
list.add(j);
}
return list;
}</integer></integer></integer></integer>

public List

    <list<integer>&gt; getFactors(int n) {
// System.out.println("get:" + n);
if(this.cache.containsKey(n)) {
return this.cache.get(n);
}</list<integer>List

    <list<integer>&gt; factors = new ArrayList
    <list<integer>&gt;();
for(int i = 2; i &lt;= n / 2; ++i) {
if(n % i != 0) {
continue;
}
// System.out.println(i);
int j = n / i;
if(i &lt;= j) {
factors.add(pair(i, j));
}
List

    <list<integer>&gt; factorsForJ = getFactors(j);
for(List<integer> factorJ : factorsForJ) {
if(factorJ.get(0) &gt;= i) {
factors.add(extendFactor(i, factorJ));
}
}
}</integer></list<integer></list<integer></list<integer>this.cache.put(n, factors);
return factors;
}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注