# 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<``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; ` `} `

/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