Generate all possible numbers which can be representated as the sum of 2 cubes below N

Question

I have written a program that generates all possible numbers which can be represented by adding 2 cubes which have value less than N

For example: when \$N = 10, 1^3 + 2^3 = 9\$

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AllNumberLessThanNasCubes {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("enter an integer n");
        int n = new Scanner(System.in).nextInt();

        System.out.println("all possible numbers are as follows ");
        generateAllPossibleNumbers(n);

    }

    /**
     * This function will generate all possible numbers less the {@link n} which can 
     * be represented as the sum of 2 cubes
     * For eg.when N=10 ,  1^3 + 2^3 = 9 
     * @param n
     */
    public static  void generateAllPossibleNumbers(int n) {
            // TODO Auto-generated method stub

    List<Long> cubes = new ArrayList<>((int) Math.cbrt(n));
    List<Long> allSum = new ArrayList<>();
    for (int i=1; Math.pow(i, 3)< n ;++i){
        cubes.add((long) Math.pow(i, 3));
    }
    long sum=0 , tempSum=0;
    int cubesSize= cubes.size();
    System.out.println(cubes);
    for (int i=0; i < cubesSize ;++i){
        sum = cubes.get(i);

        for (int j=i+1; j< cubesSize ; ++j){
            tempSum = sum + cubes.get(j) ;
            //System.out.println(tempSum);
            if (tempSum >= n){
                break;
            }else{
                allSum.add(tempSum);
            }
        }
    }
    System.out.println(allSum);
}
}

Is this the correct way to solve the problem? Is there an efficient way to solve it?

Except for error checking while taking input, what else can be improved?

Answer 1

Except for error checking

Error checking would be nice, and can easily be done, so why not add it to the top of your method:

    if (n < 0) {
        throw new IllegalArgumentException("number must not be negative");
    }

what else can be improved?

• your formatting, especially your spacing, which seems very random, and thus makes the code hard to read. Just use an IDE to fix this for you.
• define variables in as small a scope as possible. For example, sum can be declared inside the loop as long sum = cubes.get(i);.
• don't print in your method, but return the values instead. This makes the next point a lot easier, and makes your method reusable in general.
• write unit tests to verify the functionality of your code, and to make it a lot easier to make changes without being afraid of breaking the code.

Answer 2

Your code is attempting to print a list of two distinct cubes which you never mentioned in your question. Is there any reason that \$1^3 + 1^3\$ should not be in the list?

If you want to know all the numbers less than the cube root of n, would you cube each number until one is greater than n or is there a faster way?

for (int i=1; Math.pow(i, 3)< n ;++i)

Since order matters in your list (i < j), can you think of a tighter upper bound for i in the doubly nested for loop?

for (int i=0; i < cubesSize ;++i)

Some of your variable names don't fit their purpose.

sum = cubes.get(i);
tempSum = sum + cubes.get(j);

So sum was never really the sum. Maybe use

a = cubes.get(i);
b = cubes.get(j);
sum = a + b;

As an alternative design approach, in the doubly nested for loop you could calculate the maximum j for each i to eliminate the check (if(tempSum >= n) performed in your program. However with compiler branch prediction I would probably just leave it as is. You could always compare the two approaches.

Kudos for building a list of cubes though. That would not have been part of my initial design but for large N it saves a lot of redundant calculations (at the expense of memory of course).

Answer 3

Code organisation

It would probably make sense to return a list of sums instead of printing it. Also, it you do so, a set seems to be an even better idea as you wouldn't have duplicates.

Answer 4

It's more than overcomplicated. You're supposing that cubes.get(i) is faster than computing the third power. I doubt it. Moreover,

for (int i=1; i<...; ++i) {
    int square = i*i;
    ...
}

can be optimized to

for (int i=1, square=1; i<...; ++i, square+=i+i-1) {
    int square = i*i;
}

and similarly for cube. But forget, the compiler knows it well and even if not, multiplication is pretty fast on modern hardware.

So I'd bet that this straightforward method is faster:

public static void printAllCubeSumsBelow(int limit) {
    List<Long> result = new ArrayList<>();
    for (int i = 0; ; ++i) {
        long a = (long) i * i * i; // NOTE 1
        if (a >= limit) break;
        for (int j = i + 1; ; ++j) {
            long b = (long) j * j * j;
            long sum = a + b;
            if (sum >= limit) break;
            result.add(sum);
        }
    }
    System.out.println(result);
}

NOTE 1: Note that for really big n (close to Integer.MAX_VALUE) i * i * i could overflow, that's why (long ) i * i * i is needed.