Fork me on GitHub

Factor Combinations

Posted on

Description

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

1
2
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:

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

Example 1:

1
2
Input: 1
Output: []

Example 2:

1
2
Input: 37
Output:[]

Example 3:

1
2
3
4
5
6
7
Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

1
2
3
4
5
6
7
8
9
10
Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ret;
        set<int> st;
        if (n == 1) return ret;
        for (int i = 2; i <= n / 2; ++i) {
            if (st.find(i) != st.end()) continue;
            if (n % i == 0) {
                st.insert(i); st.insert(n/i);
            }
        }
        vector<int> current;
        helper(ret, st.begin(), st, n, current);
        
        return ret;
    }
    
    void helper(vector<vector<int>>& ret, 
                set<int>::iterator iter, 
                set<int>& st, int product, 
                vector<int>& current) {
        if (product == 1) {
            ret.push_back(current);
            return;
        }
        while(iter != st.end()) {
            int count = 0;
            int power = *iter;
            while(true) {
                if(product % power != 0) break;
                count += 1;
                current.push_back(*iter);
                auto nextIter = next(iter, 1);
                cout << *iter << *nextIter;
                helper(ret, nextIter, st, product/power, current); 
                power *= *iter;
            }
            while(count > 0) {
                current.pop_back();
                --count;
            }
            ++iter;
        }
        return;
    }
};

Beat 100% Solution!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ret;
        set<int> st;
        if (n == 1) return ret;
        for (int i = 2; i <= sqrt(n); ++i) {
            if (st.find(i) != st.end()) continue;
            if (n % i == 0) {
                st.insert(i); st.insert(n/i);
            }
        }
        vector<int> current;
        helper(ret, st.begin(), st, n, current);
        
        return ret;
    }
    
    void helper(vector<vector<int>>& ret, 
                set<int>::iterator iter, 
                set<int>& st, int product, 
                vector<int>& current) {
        if (product == 1) {
            ret.push_back(current);
            return;
        }
        while(iter != st.end()) {
            int count = 0;
            int power = *iter;
            while(true) {
                if(product % power != 0) break;
                count += 1;
                current.push_back(*iter);
                auto nextIter = next(iter, 1);
                helper(ret, nextIter, st, product/power, current); 
                power *= *iter;
            }
            while(count > 0) {
                current.pop_back();
                --count;
            }
            ++iter;
        }
        return;
    }
};

3 4 5