最大の積と合計がNに等しいNの4つの因子を見つけます-C++のSet-2

コンセプト

与えられた整数Nに関して、私たちのタスクは、Nのすべての因数を決定し、Nの4つの因数の積を次のように出力することです-

• 4つの要素の合計はNに等しくなります。
• 4つの要素の積が最大です。

そのような4つの要素を決定することが不可能な場合は、「不可能」と印刷することがわかっています。製品を最大化するために、4つの要素すべてを互いに等しくすることができることに注意してください。

入力

N = 60

出力

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

係数15を4回選択します

したがって、15 + 15 + 15 + 15 =60であり、製品が最大です。

メソッド

ここでは、O（P ^ 3）の複雑さをとる方法を説明しました。ここで、PはNの因子の数です。

したがって、次の手順を使用して、時間計算量O（N ^ 2）の効率的な方法を取得できます。

• 指定された数のすべての要素をコンテナに保存します。
• これで、すべてのペアを繰り返し処理し、それらの合計を別のコンテナに保存します。
• 合計が得られた要素を取得するには、インデックス（element1 + element2）をpair（element1、element2）でマークする必要があります。
• ここでも、すべてのpair_sumを反復処理し、n-pair_sumが同じコンテナーに存在するかどうかを確認します。その結果、両方のペアが4つになります。
• ペアハッシュ配列を実装して、ペアが形成された要素を取得します。
• 最後に、そのような4つのうち最大のものを保存し、最後に印刷します。

例

// C++ program to find four factors of N
// with maximum product and sum equal to N
#include <bits/stdc++.h>
using namespace std;
// Shows function to find factors
// and to print those four factors
void findfactors1(int q){
   vector<int> vec1;
   // Now inserting all the factors in a vector s
   for (int i = 1; i * i <= q; i++) {
      if (q % i == 0) {
         vec1.push_back(i);
         vec1.push_back(q / i);
      }
   }
   // Used to sort the vector
   sort(vec1.begin(), vec1.end());
   // Used to print all the factors
   cout << "All the factors are -> ";
   for (int i = 0; i < vec1.size(); i++)
      cout << vec1[i] << " ";
      cout << endl;
      // So any elements is divisible by 1
      int maxProduct1 = 1;
      bool flag1 = 1;
      // implementing three loop we'll find
      // the three largest factors
      for (int i = 0; i < vec1.size(); i++) {
         for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
               // Now storing the fourth factor in y
               int y = q - vec1[i] - vec1[j] - vec1[k];
               // It has been seen that if the fouth factor become negative
               // then break
            if (y <= 0)
               break;
            // So we will replace more optimum number
            // than the previous one
            if (q % y == 0) {
               flag1 = 0;
               maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] *y,maxProduct1);
            }
         }
      }
   }
   // Used to print the product if the numbers exist
   if (flag1 == 0)
      cout << "Product is -> " << maxProduct1 << endl;
   else
      cout << "Not possible" << endl;
}
// Driver code
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