Find the Sums of Perfect Squares in Java

The challenge

The task is simply stated. Given an integer n (3 < n < 10<sup>9</sup>), find the length of the smallest list of perfect squares which add up to n. Come up with the best algorithm you can; you’ll need it!

Examples:

• sum_of_squares(17) = 2
  17 = 16 + 1 (4 and 1 are perfect squares).
• sum_of_squares(15) = 4
  15 = 9 + 4 + 1 + 1. There is no way to represent 15 as the sum of three perfect squares.
• sum_of_squares(16) = 1
  16 itself is a perfect square.

Time constraints:

5 easy (sample) test cases: n < 20

5 harder test cases: 1000 < n < 15000

5 maximally hard test cases: 5 * 1e8 < n < 1e9

300 random maximally hard test cases: 1e8 < n < 1e9

The solution in Java code

Option 1:

import java.lang.Math;
import java.util.*;
public class SumOfSquares {
    
    public static int nSquaresFor(int n) {
        if(Math.sqrt(n)%1==0) return 1;
        while(n % 4 == 0)  n /= 4;
        if(n % 8 == 7) return 4;
        for(int i = 0; i*i < n; ++i) {
            int a = n - i*i;
            if(Math.sqrt(a)%1==0) return 2;
        }
        return 3;
    }
}

Option 2:

public class SumOfSquares {
    
    public static int nSquaresFor(int n) {
        if (Math.sqrt(n) % 1 == 0) {
            return 1;
        }
        for (int t = 1; t * t <= n; t++) {
            if (Math.sqrt(n - t * t) % 1 == 0) {
                return 2;
            }
        }
        while (n % 4 == 0) {
            n /= 4;
        }
        if(n%8 == 7) {return 4;}

        return 3;
    }
}

Option 3:

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SumOfSquares {
    public static int nSquaresFor(int n) {
        List<Integer> counts = new ArrayList<>();
        int end = (int) Math.floor(Math.sqrt(n));
        if (end*end == n){
            return 1;
        }
        for (int start = 1; start < end; start++) {
            int sum = start*start;
            int s = n - start*start;
            int count = 1;
            while (sum != n) {
                int p = (int) Math.floor(Math.sqrt(s));
                sum += p * p;
                s = n - sum;
                count++;
            }
            counts.add(count);
        }
        return counts.stream().min(Integer::compareTo).get();
    }
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest {

    @Test
    public void easyTests() {
        assertEquals(4, SumOfSquares.nSquaresFor(15));
        assertEquals(1, SumOfSquares.nSquaresFor(16));
        assertEquals(2, SumOfSquares.nSquaresFor(17));
        assertEquals(2, SumOfSquares.nSquaresFor(18));
        assertEquals(3, SumOfSquares.nSquaresFor(19));
    }
}