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) —
推荐阅读:国务院关于修改《中国公民往来台湾地区管理办法》的决定(国务院令第661号) 存款保险条例(国务院令第660号) 博物馆条例(国务院令第659号) 侵害消费者权益行为处罚办法(工商总局令第73号) 先别想着做什么网站赚钱了 先做好网站建设吧 个人网站站长应了解的基础知识 作为个人站长,何不入驻今日头条 对个人站长的一些思考 一位个人站长的自白 2020疫情将过 个人站长能否有机会赚钱
- 评论列表
-
- 添加评论