在C ++中找到具有最大乘积和等于N的四个N因子-Set-2

概念

对于给定的整数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