# Find Cube Pairs | Set 1 (A n^(2/3) Solution)

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 = 1729
Output: (1, 12) and (9, 10)
Explanation:
1729 = 1^3 + 12^3 = 9^3 + 10^3

Input: N = 4104
Output: (2, 16) and (9, 15)
Explanation:
4104 = 2^3 + 16^3 = 9^3 + 15^3

Input: N = 13832
Output: (2, 24) and (18, 20)
Explanation:
13832 = 2^3 + 24^3 = 18^3 + 20^3

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 n1/3. The idea is very simple. For every distinct pair (x, y) formed by numbers less than the n1/3, if their sum (x3 + y3) 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 = n1/3
3) for (int x = 1; x < cubeRoot; x++)
for (int y = x + 1; y <= cubeRoot; y++)
int sum = x3 + y3;
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 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 > 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; }

/div>

Output:

(2, 24) and (18, 20)

Time Complexity of above solution is O(n2/3) which is much less than O(n).

Can we solve the above problem in O(n1/3) time? We will be discussing that in next post.

## tags:

Mathematical maths-cube Mathematical