Algorithms to Compute the Factor Combinations for An Integer usi
- 时间:2020-09-25 11:32:47
- 分类:网络文摘
- 阅读:74 次
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] ]
Relevant Tool: Integer Factorization to Prime Factors with API
Integer Factor Combination via Depth First Search Algorithm
We can use the DFS (Depth First Search) Algorithm to Backtrack the integer factors. If we find a current factor (no less than its previous factor) e.g. i, we can recursively call the dfs function with n/i. The terminating condition is when n becomes 1, then we find a factor combination.
The 1 and n should be both excluded as they are not the factors. And we can avoid the duplicate combination by always searching for a factor that is not less than its previous one.
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 | class Solution { public: vector<vector<int>> getFactors(int n) { dfs(n, {}); // remove the [n] factor if (!r.empty()) r.erase(end(r), end(r) + 1); return r; } private: void dfs(int n, vector<int> cur) { if (n == 1) { if (!cur.empty()) r.push_back(cur); return; } int k = 2; if (!cur.empty()) { k = max(k, cur.back()); } for (int i = k; i <= n; ++ i) { if ((n % i) == 0) { // current is a factor cur.push_back(i); dfs(n / i, cur); cur.pop_back(); } } } vector<vector<int>> r; }; |
class Solution { public: vector<vector<int>> getFactors(int n) { dfs(n, {}); // remove the [n] factor if (!r.empty()) r.erase(end(r), end(r) + 1); return r; } private: void dfs(int n, vector<int> cur) { if (n == 1) { if (!cur.empty()) r.push_back(cur); return; } int k = 2; if (!cur.empty()) { k = max(k, cur.back()); } for (int i = k; i <= n; ++ i) { if ((n % i) == 0) { // current is a factor cur.push_back(i); dfs(n / i, cur); cur.pop_back(); } } } vector<vector<int>> r; };
Integer Factor Combinatoin via Breadth First Search Algorithm
The same backtracking algorithm can be implemented using Breadth First Search (BFS) approach. Each node in the queue is a key-value pair where key is the current number to factorize and the value is its previous combination.
Unless the current factor will be the last one, we push its children nodes to the queue.
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 | class Solution { public: vector<vector<int>> getFactors(int n) { queue<pair<int, vector<int>>> Q; Q.push({n, {}}); vector<vector<int>> r; while (!Q.empty()) { auto p = Q.front(); Q.pop(); int k = 2; if (!p.second.empty()) { k = max(k, p.second.back()); } for (int i = k; i <= p.first; ++ i) { if (p.first % i == 0) { vector<int> next(p.second); next.push_back(i); if (p.first / i == 1) { // the last factor if (next[0] != n) { r.push_back(next); } } else { Q.push({p.first / i, next}); } } } } return r; } }; |
class Solution { public: vector<vector<int>> getFactors(int n) { queue<pair<int, vector<int>>> Q; Q.push({n, {}}); vector<vector<int>> r; while (!Q.empty()) { auto p = Q.front(); Q.pop(); int k = 2; if (!p.second.empty()) { k = max(k, p.second.back()); } for (int i = k; i <= p.first; ++ i) { if (p.first % i == 0) { vector<int> next(p.second); next.push_back(i); if (p.first / i == 1) { // the last factor if (next[0] != n) { r.push_back(next); } } else { Q.push({p.first / i, next}); } } } } return r; } };
Both approaches will need to complete the search to find all possible factor combination. The BFS is iterative and thus free of stack-over-flow risk that the Recursive DFS may have.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:回归自然——小花猪2 小黑野猪——小花猪3 人猪大战——小花猪4 网站建设容易忽略的6个地方 如何检查网站是否被竞争对手Negative SEO攻击? 站长创业经验分享 屌丝站长的平凡创业路 如何做让站长赚钱更容易?做好网站浏览体验 奇妙的虹吸现象|小学作文 布达拉宫|小学作文
- 评论列表
-
- 添加评论