Given a large number N, find all positive numbers less than N that can be represented as sum of two cubes for at-least two different pairs.

In other words, find all positive numbers M less than given number N that can be expressed as

M = (a^3 + b^3) = (c^3 + d^3) for distinct a, b, c, d.

For example, if N = 25000, M can be any of 1729, 4104, 13832 or 20683 as these numbers can be represented as sum of two cubes for two different pairs.

1729 = 1^3 + 12^3 = 9^3 + 10^3

4104 = 2^3 + 16^3 = 9^3 + 15^3

13832 = 2^3 + 24^3 = 18^3 + 20^3

20683 = 10^3 + 27^3 = 19^3 + 24^3

The idea is very simple and effective. We know that any number M that satisfies the constraint will have two distinct pairs (lets say (a, b) and (c, d)). If we observe, since M < N, we can say that a, b, c and d are less than *N ^{1/3}*. Now for every distinct pair (x, y) formed by numbers less than the

*N*, we store their sum (x

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

^{3}) in a set. If two pairs with same sum exists, we simply print the sum.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <bits/stdc++.h> using namespace std; void findAllNumbers(int N) { // find cube root of N int cb = pow(N, 1.0 / 3); // create an empty set set<int> s; for (int i = 1; i < cb - 1; i++) { for (int j = i + 1; j < cb; j++) { // (i, j) forms a pair int sum = (i * i * i) + (j * j * j); // sum is seen before if (s.find(sum) != s.end()) cout << sum << endl; else // sum is not seen before s.insert(sum); } } } // main function int main() { int N = 25000; findAllNumbers(N); return 0; } |

**Output: **

1729

4104

13832

20683

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

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply