Fewest Perfect Squares That Sum to n

/*
 * Problem : Fewest squares.
 * Input   : n.
 * Output  : The count.
 * Approach: Four-square theorem.
 * Time    : O(sqrt n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        private static boolean isSquare(long x) {
            long root = (long) Math.sqrt((double) x);
            while (root * root > x) {
                root--;
            }
            while ((root + 1) * (root + 1) <= x) {
                root++;
            }
            return root * root == x;
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: Lagrange's theorem: every number is a sum of at most 4 squares. So the answer is 1, 2, 3 or 4.
        if (isSquare(n)) {
            return 1;
        }
        // Step 2: The answer is 4 exactly when n has the form 4^k * (8m + 7). Remove the factors of 4 first.
        long reduced = n;
        while (reduced % 4 == 0) {
            reduced /= 4;
        }
        if (reduced % 8 == 7) {
            return 4;
        }
        // Step 3: Check if n is the sum of two squares. If not, the answer is 3.
        for (long i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) {
                return 2;
            }
        }
        return 3;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}