kennelcrash
BAN USERimport java.util.*;
public class Main {
private static Map<Integer, Pair[]> cubeSum(int n) {
Map<Integer, Pair[]> result = new HashMap<>();
int nCube = (int) Math.cbrt(n);
int[] relevant = new int[nCube];
relevant[nCube - 1] = n;
for(int i = 1; i < nCube; ++i) {
relevant[i - 1] = (int) Math.pow(i, 3);
}
for(int i = 1; i < n; ++i) {
cubeSum(i, result, relevant);
}
return result;
}
private static void cubeSum(int n, Map<Integer, Pair[]> result, int[] relevant) {
int count = 0;
int left = 0, right = 0;
while(relevant[right + 1] < n) {
++right;
}
Pair[] sums = new Pair[2];
while(left < right) {
if(relevant[left] + relevant[right] < n) {
++left;
} else if(relevant[left] + relevant[right] > n) {
--right;
} else {
sums[count] = new Pair(relevant[left], relevant[right]);
++count;
if(count == 2) {
result.put(n, sums);
return;
}
++left;
--right;
}
}
}
private static void printResult(Map<Integer, Pair[]> result) {
for(Map.Entry<Integer, Pair[]> entry: result.entrySet()) {
int key = entry.getKey();
Pair[] values = entry.getValue();
System.out.println(key + " may be represented as " + values[0] + " and " + values[1]);
}
}
public static void main(String... args) {
Map<Integer, Pair[]> result = cubeSum(20000);
printResult(result);
}
}
public class Pair {
int a;
int b;
int aCube;
int bCube;
public Pair(int aNew, int bNew) {
if(aNew >= bNew) {
int temp = aNew;
aNew = bNew;
bNew = temp;
}
this.a = (int) Math.cbrt(aNew);
this.b = (int) Math.cbrt(bNew);
this.aCube = aNew;
this.bCube = bNew;
}
@Override
public String toString() {
return a + "^3" + " + " + b + "^3 (" + aCube + " + " + bCube + ")";
}
}
Unlike most of the other answers, this code solves the defined problem. The complexity is O( n^(4/3) ).
- kennelcrash November 15, 2015
People should realize that this question has a lower bound of O(n^2). Imagine the list {1, 2, 3, 4, 5, 6} and the number 5000 as k. In this case all of the numbers can be combined so we need to print 1 + 2 + ... + n - 1 = n * (n + 1) / 2 ( = O(n^2) )combinations.
- kennelcrash November 15, 2015