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 [closed]

Question

Looking for an algorithm or some coding hints to find the solutions for

a^3 + b^3 = c^3 + d^3, where a, b, c and d all are in the range [1 .. 10000]

It's an interview question.

I'm thinking priority queues to at least iterate for a and b values. Some hint will be great, will try to work through from there.

Answer 1

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⁽¹⁾ 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.

Answer 2

Using a priority queue is almost certainly the simplest solution, and also the most practical one, since it's O(n) storage (with a log factor if you require bignums). Any solution which involves computing all possible sums and putting them in a map will require O(n^2) storage, which soon becomes impractical.

My naive, non-optimized implementation using a priority queue is O(n^2 log(n)) time. Even so, it took less than five seconds for n = 10000 and about 750 seconds for n = 100000, using a couple of megabytes of storage. It certainly could be improved.

The basic idea, as per your comment, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution. (I could paste the code, but you only asked for a hint.)

Answer 3

Using Hashmap (O(n^2) solution):

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import static java.lang.Math.pow;

/**
 * Created by Anup on 10-10-2016.
 */

class Pair {
    int a;
    int b;

    Pair(int x, int y) {
        a = x;
        b = y;
    }
}

public class FindCubePair {
    public static void main(String[] args) {
        HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
        int n = 100000;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                long sum = (long) (pow(i, 3) + pow(j, 3));

                if(hashMap.containsKey(sum)) {
                    List<Pair> list = hashMap.get(sum);
                    for(Pair p : list) {
                        System.out.println(i + " " + j + " " + p.a + " " + p.b);
                    }
                } else {
                    ArrayList<Pair> list = new ArrayList<>();
                    hashMap.put(sum, list);
                }

                hashMap.get(sum).add(new Pair(i, j));
            }
        }
    }
}

Unfortunately, the value of integers printed does not even reach 1000 on my computer due to resource limitation.