Find four factors of N with maximum product and sum equal to N - Set-2 in C++

Concept

With respect of a given integer N, our task is to determine all factors of N and print the product of four factors of N so that −

• The sum of the four factors is equal to N.
• The product of the four factors is largest.

It has been seen that if it is impossible to determine 4 such factors then print “Not possible”. It should be noted thatall the four factors can be equal to each other to maximize the product.

Input

N = 60

Output

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

Select the factor 15 four times,

Therefore, 15+15+15+15 = 60 and product is largest.

Method

Here a method which takes a complexity of O(P^3), where P is the number of factors of N has been explained.

So an efficient method of time complexity O(N^2) can be obtained with the help of following steps.

• We store all the factors of given number in a container.
• Now we iterate for all pairs and store their sum in a different container.
• We have to mark the index (element1 + element2) with pair(element1, element2) to obtain the elements by which the sum was obtained.
• Again we iterate for all the pair_sums, and verify if n-pair_sum exists in the same container, as a result both the pairs form the quadruple.
• Implement the pair hash array to obtain the elements by which the pair was formed.
• Finally, store the largest of all such quadruples, and print it at the end.

Example

 Live Demo

// 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; }

Output

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