对于给定的整数N,我们的任务是确定N的所有因子,并打印N的四个因子的乘积,以便-
这四个因子的总和等于N。
这四个因素的乘积最大。
已经看到,如果不可能确定4个这样的因素,则打印“不可能”。应该注意的是,所有四个因素可以彼此相等,以使乘积最大化。
N = 60
输出结果
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625
选择因子15的四倍,
因此,15 + 15 + 15 + 15 = 60并且乘积最大。
在这里,已经说明了一种复杂度为O(P ^ 3)的方法,其中P是N的因数。
因此,可以通过以下步骤获得一种有效的时间复杂度O(N ^ 2)方法。
我们将给定数量的所有因子存储在一个容器中。
现在,我们对所有对进行迭代,并将它们的和存储在不同的容器中。
我们必须用对(element1,element2)标记索引(element1 + element2),以获得获得总和的元素。
再次,我们对所有pair_sums进行迭代,并验证n-pair_sum是否存在于同一容器中,结果这两个对都构成了四对。
实现对散列数组,以获取形成该对的元素。
最后,存储所有此类四元组中最大的一组,并在最后打印。
// C++ program to find four factors of N //最大乘积和等于N- #include <bits/stdc++.h> using namespace std; //显示功能以查找因素 //并打印这四个因素 void findfactors1(int q){ vector<int> vec1; //现在将所有因子插入向量s- for (int i = 1; i * i <= q; i++) { if (q % i == 0) { vec1.push_back(i); vec1.push_back(q / i); } } //用于对向量进行排序 sort(vec1.begin(), vec1.end()); //用于打印所有因素 cout << "All the factors are -> "; for (int i = 0; i < vec1.size(); i++) cout << vec1[i] << " "; cout << endl; //所以任何元素都可以被1整除 int maxProduct1 = 1; bool flag1 = 1; //实现三个循环,我们将发现 //三大因素 for (int i = 0; i < vec1.size(); i++) { for (int j = i; j < vec1.size(); j++) { for (int k = j; k < vec1.size(); k++) { //现在将第四个因子存储在y- int y = q - vec1[i] - vec1[j] - vec1[k]; //已经看到,如果泡沫因子变为负 //然后打破 if (y <= 0) break; //因此,我们将替换更多的最佳数字 //比上一个 if (q % y == 0) { flag1 = 0; maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] *y,maxProduct1); } } } } //如果存在数字,则用于打印产品 if (flag1 == 0) cout << "Product is -> " << maxProduct1 << endl; else cout << "Not possible" << endl; } //驱动程式码 int main(){ int q; q = 60; findfactors1(q); return 0; }
输出结果
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625