एक नंबर दिया गया है। हमें दो पेयर्स ढूंढने हैं जो उस नंबर को दो क्यूब्स के योग के रूप में दर्शा सकें। इसलिए हमें दो पेयर्स (a, b) और (c, d) ढूंढने हैं जैसे कि दिया गया नंबर n इस प्रकार व्यक्त हो: n = a³ + b³ = c³ + d³
विचार सरल है। यहां हर नंबर a, b, c और d सभी n¹ᐟ³ से कम हैं। n¹ᐟ³ से कम नंबर्स द्वारा बने हर डिस्टिंक्ट पेयर (x, y) के लिए, यदि उनका योग (x³ + y³) दिए गए नंबर के बराबर है, तो हम उन्हें हैश टेबल में योग मान को की के रूप में स्टोर करते हैं, फिर यदि वही योग फिर से आता है, तो बस प्रत्येक पेयर को प्रिंट करें।
एल्गोरिदम
getPairs(n): begin cube_root := n का क्यूब रूट इंट टाइप की और पेयर टाइप वैल्यू वाला मैप i को 1 से cube_root तक की रेंज में, करें j को i + 1 से cube_root तक की रेंज में, करें sum = i³ + j³ यदि sum n के समान नहीं है, तो अगला भाग छोड़ें, दूसरी इटरेशन पर जाएं यदि sum मैप में मौजूद है, तो पेयर और (i, j) प्रिंट करें, अन्यथा संबंधित sum के साथ (i,j) मैप में इन्सर्ट करें done done end
उदाहरण
#include <iostream> #include <cmath> #include <map> using namespace std; int getPairs(int n){ int cube_root = pow(n, 1.0/3.0); map<int, pair<int, int> > my_map; for(int i = 1; i<cube_root; i++){ for(int j = i + 1; j<= cube_root; j++){ int sum = i*i*i + j*j*j; if(sum != n) continue; if(my_map.find(sum) != my_map.end()){ cout << "(" << my_map[sum].first << ", " << my_map[sum].second << ") and (" << i << ", " << j << ")" << endl; }else{ my_map[sum] = make_pair(i, j); } } } } int main() { int n = 13832; getPairs(n); }आउटपुट
(2, 24) and (18, 20)