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.
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.
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.)
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.
A quicker than trivial solution is as follows: You calculate all values that a^3 + b^3 can have, and store all possible values of a and b with it. This is done by looping through a and b, storing the results (a^3 + b^3) in a binary tree and having a list of values (a's and b's) associated to each result.
After this step, you need to traverse the list and for each value, choose every possible assignment for a,b,c,d.
I think this solution takes O(n^2 log n) time and O(n^2) space, but i might be missing something.
int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
int a3 = a * a * a;
if(a3 > MAX) break;
for(int b = a; b < MAX; b ++){
int b3 = b * b * b;
if(a3 + b3 > MAX)break;
for(int c = 0; c < a; c++){
int c3 = c*c*c;
int m = a3 - c3;
int d = b+1;
while(true){
int d3 = d * d * d;
if(d3-b3 <= m){
if((d3 - b3) == m){
count++;
PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
}
d++;
continue;
}
else
break;
}
}
}
}
return 0;
}
Let's assume a solution:
a=A, b=B, c=C, and d=D.
Given any solution we can generate another 3 solutions
abcd
ABCD
ABDC
BACD
BADC
Actually, if A=B, or C=D, then we might only have 1 or 2 further solutions.
We can choose the solutions we look for first by ordering A <= B and C <= D. This will reduce the search space. We can generate the missed solutions from the found ones.
There will always be at least one solution, where A=C and B=D. What we're looking for is when A>C and B<D. This comes from the ordering: C can't be greater than A because, as we've chosen to only look at solutions where D>C, the cube sum would be too big.
We can calculate A^3 + B^3, put it in a map as the key, with a vector of pairs A,B as the value.
There will be (n^2)/2 values.
If there are already values in the vector they will all have lower A and they are the solutions we're looking for. We can output them immediately, along with their permutations.
I'm not sure about complexity.
One Solution - using concept of finding 2 sum in a sorted array. This is O(n3)
public static void pairSum() {
int SZ = 100;
long[] powArray = new long[SZ];
for(int i = 0; i< SZ; i++){
int v = i+1;
powArray[i] = v*v*v;
}
int countPairs = 0;
int N1 = 0, N2 = SZ-1, N3, N4;
while(N2 > 0) {
N1=0;
while(N2-N1 > 2) {
long ts = powArray[N1] + powArray[N2];
N3 = N1+1; N4 = N2-1;
while(N4 > N3) {
if(powArray[N4]+powArray[N3] < ts) {
N3++;
}else if(powArray[N4]+powArray[N3] > ts) {
N4--;
}else{
//System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
countPairs++;
break;
}
}
N1++;
}
N2--;
}
System.out.println("quadruplet pair count:"+countPairs);
}
Logic :
a^3 + b^3 = c^3 + d^3
Then, a^3+b^3-c*3-d^3 = 0
Try to solve this equation by putting all combination of values for a,b,c and d in range of [0 , 10^5].
If equation is solved print the values of a,b,c and d
public static void main(String[] args) {
//find all solutions of a^3 + b^3 = c^3 + d^3
double power = 3;
long counter = 0; // to count the number of solution sets obtained
int limit = 100000; // range from 0 to limit
//looping through every combination of a,b,c and d
for(int a = 0;a<=limit;a++)
{
for(int b = 0;b<=limit;b++)
{
for(int c = 0;c<=limit;c++)
{
for(int d = 0;d<=limit;d++)
{
// logic used : a^3 + b^3 = c^3 + d^3 can be written as a^3 + b^3 - c^3 - d^3 = 0
long result = (long)(Math.pow(a,power ) + Math.pow(b,power ) - Math.pow(c,power ) - Math.pow(d,power ));
if(result == 0 )
{
counter++; // to count the number of solutions
//printing the solution
System.out.println( "a = "+ a + " b = " + b + " c = " + c + " d = " + d);
}
}
}
}
}
//just to understand the change in number of solutions as limit and power changes
System.out.println("Number of Solutions =" + counter);
}
Starting with the brute force approach, its pretty obvious it will O(n^4) time to execute. If space is not a constraint, we can go for combination of list and maps. The code is self-explanatory, we are using a nested list to keep track of all entries for a particular sum (key in map). The time complexity is thus reduced from O(n^4) to O(n^2)
public void printAllCubes() {
int n = 50;
Map<Integer, ArrayList<ArrayList>> resMap = new HashMap<Integer, ArrayList<ArrayList>>();
ArrayList pairs = new ArrayList<Integer>();
ArrayList allPairsList = new ArrayList<ArrayList>();
for (int c = 1; c < n; c++) {
for (int d = 1; d < n; d++) {
int res = (int) (Math.pow(c, 3) + Math.pow(d, 3));
pairs.add(c);
pairs.add(d);
if (resMap.get(res) == null) {
allPairsList = new ArrayList<ArrayList>();
} else {
allPairsList = resMap.get(res);
}
allPairsList.add(pairs);
resMap.put(res, allPairsList);
pairs = new ArrayList<Integer>();
}
}
for (int a = 1; a < n; a++) {
for (int b = 1; b < n; b++) {
int result = (int) (Math.pow(a, 3) + Math.pow(b, 3));
ArrayList<ArrayList> pairList = resMap.get(result);
for (List p : pairList) {
System.out.print(a + " " + b + " ");
for (Object num : p)
System.out.print(num + " ");
System.out.println();
}
}
}
}
