Perfect Squares

NeetCode: Perfect Squares · LeetCode: 279. Perfect Squares · Difficulty: Medium

Given a positive integer n (small enough that j * j never overflows an int), return the least number of perfect square numbers (1, 4, 9, 16, ...) that sum to n.

Example

Text

Input:  n = 12    Output: 3    (4 + 4 + 4)
Input:  n = 13    Output: 2    (4 + 9)

Brute force: try every square, recursively

The last square in a decomposition of n is some j*j <= n. Try each one and solve the smaller problem n - j*j, taking the minimum plus one. Without caching, the same remainders are solved repeatedly, so the recursion is exponential.

Java

class Solution {
    public int numSquares(int n) {
        if (n == 0) {
            return 0;
        }
        int best = Integer.MAX_VALUE;
        for (int j = 1; j * j <= n; j++) {
            best = Math.min(best, 1 + numSquares(n - j * j));
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numSquares(12));
        System.out.println(solution.numSquares(13));
        System.out.println(solution.numSquares(1));
    }
}

Output

3
2
1

Time: exponential (each call branches into up to sqrt(n) calls, depth up to n). Space: O(n) recursion depth.

Better: bottom-up DP

Let dp[i] be the answer for i, with dp[0] = 0. Then dp[i] = 1 + min(dp[i - j*j]) over all squares j*j <= i. Each of the n cells looks at sqrt(n) squares. The unreached cells hold Integer.MAX_VALUE; dp[i - j * j] + 1 never reads one, because j = 1 always reaches a finished cell.

Java

import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numSquares(12));
        System.out.println(solution.numSquares(13));
        System.out.println(solution.numSquares(1));
    }
}

Output

3
2
1

Time: O(n * sqrt(n)). Space: O(n).

Optimal: Lagrange's four-square theorem

Lagrange proved that every non-negative integer is a sum of at most four squares, so the answer is always 1, 2, 3 or 4. Legendre's three-square theorem states that the answer is 4 exactly when n = 4^a * (8b + 7). The remaining cases are tested in order:

If n is a perfect square, the answer is 1.
Strip all factors of 4 from n; if the remainder is 7 mod 8, the answer is 4.
If n = x*x + y*y for some x, the answer is 2 (checked in O(sqrt(n))). isSquare takes the floating-point Math.sqrt and corrects it by one step in each direction, so the answer is exact even if the double result is off by one.
Otherwise the answer is 3.

Java

class Solution {
    private boolean isSquare(long n) {
        long r = (long) Math.sqrt((double) n);
        while (r * r > n) {
            r--;
        }
        while ((r + 1) * (r + 1) <= n) {
            r++;
        }
        return r * r == n;
    }

    public int numSquares(int n) {
        if (isSquare(n)) {
            return 1;
        }
        int m = n;
        while (m % 4 == 0) {
            m /= 4;
        }
        if (m % 8 == 7) {
            return 4;
        }
        for (long x = 1; x * x < n; x++) {
            if (isSquare(n - x * x)) {
                return 2;
            }
        }
        return 3;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numSquares(12));
        System.out.println(solution.numSquares(13));
        System.out.println(solution.numSquares(1));
        System.out.println(solution.numSquares(7));
    }
}

Output

Time: O(sqrt(n)). Space: O(1).