अवधारणा
किसी दिए गए पूर्णांक 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) की एक कुशल विधि निम्नलिखित चरणों की सहायता से प्राप्त की जा सकती है।
- हम दी गई संख्या के सभी गुणनखंडों को एक कंटेनर में संग्रहीत करते हैं।
- अब हम सभी जोड़ियों के लिए पुनरावृति करते हैं और उनके योग को एक अलग कंटेनर में संग्रहीत करते हैं।
- हमें उन तत्वों को प्राप्त करने के लिए जोड़ी (एलिमेंट 1, एलिमेंट 2) के साथ इंडेक्स (एलिमेंट 1 + एलिमेंट 2) को चिह्नित करना होगा, जिनके द्वारा योग प्राप्त किया गया था।
- फिर से हम सभी जोड़ी_समों के लिए पुनरावृति करते हैं, और सत्यापित करते हैं कि क्या n-pair_sum एक ही कंटेनर में मौजूद है, परिणामस्वरूप दोनों जोड़े चौगुनी बनते हैं।
- जोड़ी हैश सरणी को उन तत्वों को प्राप्त करने के लिए लागू करें जिनके द्वारा जोड़ी बनाई गई थी।
- आखिरकार, ऐसे सभी चौपाइयों में से सबसे बड़ा स्टोर करें और अंत में प्रिंट करें।
उदाहरण
// 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