An interview without using external libraries is constrained, and it depends on what skills you want to show off. In this case we know that a greedy algorithm will not work, and the answer is 1 to 4 (due to Lagrange's four square theorem).
Thus a fast solution is:
class Main {
private static boolean FourSquaresNeeded(int n) {
// According to https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
if (n % 4!=0) return (n % 8) == 7;
else return FourSquaresNeeded(n / 4);
}
public static int solution(int n){
// Assume that n>0
// According to https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem 4 is the most, and there's a formula when four is needed
if (FourSquaresNeeded(n)) return 4;
// We now know that answer is 1..3
int nsqrt = (int)Math.sqrt(n); // Truncating
if (nsqrt * nsqrt == n) return 1;
// Since it wasn't a square we know that the answer is 2..3, and 2 means a sum of two squares so check that:
int lower = (int)Math.sqrt(n / 2);
// starting from avoid double-counting the squares
for (int i = lower; i <= nsqrt;i++) {
int restsq = (n - i * i);
int rest = (int)Math.sqrt(restsq);
if (rest* rest == restsq) return 2; // A sum of two squares.
}
// Not a square, not sum of two squares and not the messy answer requiring 4, so:
return 3;
}
}
Note that it doesn't find the needed squares, just the number of square needed.
