अवधारणा
एक दिए गए पूर्णांक N के संबंध में, हमारा कार्य N के सभी गुणनखंड निर्धारित करना है और N के चार गुणनखंडों का गुणनफल प्रिंट करना है ताकि −
<उल क्लास="सूची"><ली>चार गुणनखंडों का योग N के बराबर हो।ली><ली>चार गुणनखंडों का गुणनफल सबसे बड़ा हो।ली>उल>यह देखा गया है कि यदि ऐसे 4 गुणनखंड निर्धारित करना असंभव है तो "Not possible" प्रिंट करें। यह ध्यान दिया जाना चाहिए कि उत्पाद को अधिकतम करने के लिए सभी चार गुणनखंड एक-दूसरे के बराबर हो सकते हैं।
इनपुट
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-जोड़ी_योग उसी कंटेनर में मौजूद है या नहीं, परिणामस्वरूप दोनों जोड़ चौगुना बनाते हैं।ली><ली>तत्वों को प्राप्त करने के लिए जोड़ी हैश सरणी लागू करें जिनसे जोड़ी बनी थी।ली><ली>अंत में, ऐसे सभी चौगुने में से सबसे बड़े को संग्रहीत करें, और अंत में इसे प्रिंट करें।ली>उल>उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ program to find four factors of N // with maximum product and sum equal to N #include <bits/stdc++.h> using namespace std; // गुणनखंड खोजने और उन चार गुणनखंडों को प्रिंट करने वाला फ़ंक्शन void findfactors1(int q){ vector<int> vec1; // अब एक वेक्टर में सभी गुणनखंड डालें 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