# Find numbers represented as sum of two cubes for two different pairs

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 N1/3. Now for every distinct pair (x, y) formed by numbers less than the N1/3, we store their sum (x3 + y3) in a set. If two pairs with same sum exists, we simply print the sum.

## C++

Output:

1729
4104
13832
20683

The time Complexity of above solution is O(n2/3).

(1 votes, average: 5.00 out of 5)