최대 곱과 합이 N과 같은 N의 4개 인수 찾기 - C++의 Set-2

컨셉

주어진 정수 N과 관련하여 우리의 임무는 N의 모든 인수를 결정하고 N의 인수와 곱하여 다음과 같이 출력하는 것입니다. -

• 네 가지 요소의 합은 N과 같습니다.
• 네 가지 요인의 곱이 가장 큽니다.

그러한 4가지 요소를 결정하는 것이 불가능하면 "불가능"이라고 인쇄하는 것으로 나타났습니다. 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이고 제품이 가장 큽니다.

방법

여기에서 P는 N의 인수의 수인 O(P^3)의 복잡성을 취하는 방법이 설명되었습니다.

따라서 다음 단계를 통해 시간 복잡도 O(N^2)의 효율적인 방법을 얻을 수 있습니다.

• 주어진 수의 모든 인수를 컨테이너에 저장합니다.
• 이제 모든 쌍에 대해 반복하고 합계를 다른 컨테이너에 저장합니다.
• 합계를 구한 요소를 얻으려면 인덱스(요소1 + 요소2)를 쌍(요소1, 요소2)으로 표시해야 합니다.
• 다시 모든 pair_sums에 대해 반복하고 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