घन जोड़े खोजें - (A n^(2/3) Solution) C++ . में

एक नंबर दिया गया है। हमें दो जोड़े खोजने हैं, जो दो घनों के योग के रूप में संख्या का प्रतिनिधित्व कर सकते हैं। अतः हमें दो जोड़े (a, b) और (c, d) इस प्रकार ज्ञात करने हैं कि दी गई संख्या n को n =a ³ के रूप में व्यक्त किया जा सके। + ख ³ =सी ³ + डी ³

विचार सरल है। यहाँ प्रत्येक संख्या a, b, c और d सभी n से कम हैं ^1/3 . n ^1/3 . से कम संख्या से बनने वाले प्रत्येक विशिष्ट जोड़े (x, y) के लिए , यदि उनका योग (x ³ + y ³ ) दी गई संख्या के बराबर है, हम उन्हें कुंजी के रूप में योग मान के साथ हैश तालिका में संग्रहीत करते हैं, फिर यदि वही योग फिर से आता है, तो वे बस प्रत्येक जोड़ी को प्रिंट करते हैं

एल्गोरिदम

getPairs(n):
begin
   cube_root := cube root of n
   map as int type key and pair type value
   for i in range 1 to cube_root, do
      for j in range i + 1 to cube_root, do
         sum = i3 + j3
         if sum is not same as n, then skip next part, go to second iteration
         if sum is present into map, then print pair, and (i, j),
         else insert (i,j) with corresponding sum into the map
      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)