Find all the quadruples [a, b, c, d] where a^3 + b^3 = c^3 + d^3 when 1 <= a, b, c or d <= 10000

algorithm, complexity-theory

Solution

Using a hash map to store the `(cube,(a,b))`, you can iterate all possible pairs of integers, and output a solution once you have found that the required sum of cubes is already in the map.

pseudo code:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution            
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))  

This solution is O(n^2) space(1) and O(n^2 + OUTPUT) time on average, where OUTPUT is the size of the output.

EDIT:

Required space is actually `O(n^2 logn)`, where `n` is the range (10^5), because to represent `10^5` integers you need `ceil(log_2(10^15)) = 50` bits. So, you actually need something like 500,000,000,000 bits (+ overhead for map and list) which is ~58.2 GB (+ overhead).

Since for most machines it is a bit too much - you might want to consider storing the data on disk, or if you have 64bits machine - just store in into "memory" and let the OS and virtual memory system do this as best as it can.

(1) As the edit clarifies, it is actually `O(n^2log(n))` space, however if we take each integer storage as `O(1)` (which is usually the case) we get `O(n^2)` space. Same principle will apply for the time complexity, obviously.

Problem

Original source