Given a number n, find two pairs that can represent the number as sum of two cubes. In other words, find two pairs (a, b) and (c, d) such that given number n can be expressed as

n = a^3 + b^3 = c^3 + d^3

where a, b, c and d are four distinct numbers.

Examples:

Input:N = 1729Output:(1, 12) and (9, 10)Explanation:1729 = 1^3 + 12^3 = 9^3 + 10^3Input:N = 4104Output:(2, 16) and (9, 15)Explanation:4104 = 2^3 + 16^3 = 9^3 + 15^3Input:N = 13832Output:(2, 24) and (18, 20)Explanation:13832 = 2^3 + 24^3 = 18^3 + 20^3

Any number n that satisfies the constraint will have two distinct pairs (a, b) and (c, d) such that a, b, c and d are all less than *n ^{1/3}*. The idea is very simple. For every distinct pair (x, y) formed by numbers less than the

*n*, if their sum (x

^{1/3}^{3}+ y

^{3}) is equal to given number, we store them in a hash table using sum as a key. If pairs with sum equal to given number appears again, we simply print both pairs.

1) Create an empty hash map, say s. 2) cubeRoot = n^{1/3}3) for (int x = 1; x < cubeRoot; x++) for (int y = x + 1; y <= cubeRoot; y++) int sum = x^{3}+ y^{3}; if (sum != n) continue; if sum exists in s, we found two pairs with sum, print the pairs else insert pair(x, y) in s using sum as key

Below is C++ implementation of above idea –

`// C++ program to find pairs that can represent ` `// the given number as sum of two cubes ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Function to find pairs that can represent ` `// the given number as sum of two cubes ` `void` `findPairs(` `int` `n) ` `{ ` ` ` `// find cube root of n ` ` ` `int` `cubeRoot = ` `pow` `(n, 1.0/3.0); ` ` ` ` ` `// create an empty map ` ` ` `unordered_map<` `int` `, pair<` `int` `, ` `int` `> > s; ` ` ` ` ` `// Consider all pairs such with values less ` ` ` `// than cuberoot ` ` ` `for` `(` `int` `x = 1; x < cubeRoot; x++) ` ` ` `{ ` ` ` `for` `(` `int` `y = x + 1; y <= cubeRoot; y++) ` ` ` `{ ` ` ` `// find sum of current pair (x, y) ` ` ` `int` `sum = x*x*x + y*y*y; ` ` ` ` ` `// do nothing if sum is not equal to ` ` ` `// given number ` ` ` `if` `(sum != n) ` ` ` `continue` `; ` ` ` ` ` `// if sum is seen before, we found two pairs ` ` ` `if` `(s.find(sum) != s.end()) ` ` ` `{ ` ` ` `cout << ` `"("` `<< s[sum].first << ` `", "` ` ` `<< s[sum].second << ` `") and ("` ` ` `<< x << ` `", "` `<< y << ` `")"` `<< endl; ` ` ` `} ` ` ` `else` ` ` `// if sum is seen for the first time ` ` ` `s[sum] = make_pair(x, y); ` ` ` `} ` ` ` `} ` `} ` ` ` `// Driver function ` `int` `main() ` `{ ` ` ` `int` `n = 13832; ` ` ` `findPairs(n); ` ` ` `return` `0; ` `} ` |

Output:

(2, 24) and (18, 20)

**Time Complexity** of above solution is O(n^{2/3}) which is much less than O(n).

Can we solve the above problem in O(n^{1/3}) time? We will be discussing that in next post.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments