Least Number of Perfect Squares that Sums to n

Given a number “n”, find the least number of perfect square numbers that sum to n

For Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

Let’s take n=12. How many ways we can find n by summing up perfect squares less than n? Note that, maximum perfect square less then n will be √n. So, we can check for each numbers in j=1 to √n whether we can break n into two parts such that one part is a perfect square j*j and the remaining part n-j*j can be broken into perfect squares in similar manner. Clearly it has a recurrence relation ps(n)=j*j+ps(n-j*j), for all possible 1≤j≤√n. We need to find such j that minimizes number of perfect squares generated.

Note the recursion tree generated for the recurrence relation ps(n)=j*j+ps(n-j*j), for all possible 1≤j≤√n for n = 12. We can clearly see that we can reach solution in many paths but the least number of perfect squares that sums to n=12 is ps(12) = 2^2+2^2+2^2 which has 3 perfect squares. Also, note that the problem has repeating subproblems. For example, ps(2), ps(7), and ps(3) is appearing twice. So, intuition tells us that as the problem has optima substructure ps(n)=j*j+ps(n-j*j), for all possible 1≤j≤√n and it has repeating subproblems, so we can use DP to solve the exponential expansion of the recursion tree.

O(n^2) DP solution

Let, PSN(i) is minimum number of perfect squares that sum to i
PSN(i) = min{1+PSN(i-j*j)}, for all j, 1≤j≤√i

Below is a simple implementation of the above DP solution to the least number of perfect sum problem. This runs in O(n^2).

public static int perfectSquareDP(int n){
	if(n <= 0){
		return 0;
	}
	
	int[] dp = new int[n+1];
	Arrays.fill(dp, Integer.MAX_VALUE);
	dp[0] = 0;
	dp[1] = 1;
	
	//to compute least perfect for n we compute top down for each 
	//possible value sum from 2 to n
	for(int i = 2; i<=n; i++){
		//for a particular value i we can break it as sum of a perfect square j*j and 
		//all perfect squares from solution of the remainder (i-j*j)
		for(int j = 1; j*j<=i; j++){
			dp[i] = Math.min(dp[i], 1+dp[i-j*j]);
		}
	}
	
	return dp[n];
}

Fastest Solution – Lagrange’s four-square theorem
Lagrange’s four-square theorem, also known as Bachet’s conjecture, states that every natural number can be represented as the sum of four integer squares.

p = a_0^2 + a_1^2 + a_2^2 + a_3^2
where the four numbers a_0, a_1, a_2, a_3 are integers. For illustration, 3, 31 and 310 can be represented as the sum of four squares as follows:

3 = 1^2+1^2+1^2+0^2
31 = 5^2+2^2+1^2+1^2
310 = 17^2+4^2+2^2+1^2

This theorem was proved by Joseph Louis Lagrange in 1770. Adrien-Marie Legendre completed the theorem in 1797–8 with his three-square theorem, by proving that a positive integer can be expressed as the sum of three squares if and only if it is not of the form 4^k(8m+7) for integers k and m.

This basically tells us that any number can be broken into maximum of 4 squares. So, by default this is our answer. we need to check if we have a solution with 3 or 2 or 1 squares. There can be a 3-square solution if and only if we can’t write n in the form 4^k(8m+7) for integers k and m. If a number itself is a perfect square number then numbers of square is 1. Otherwise we can try break the number into 2 squares i and j such that n=i*i+j*j, for any i, 1≤i≤√n. So, for any natural positive number there are only 4 possible results: 1, 2, 3, 4.

Below is a O(√n) time solution using the above math based solution.

private static boolean is_square(int n){  
    int sqrt_n = (int)(Math.sqrt(n));  
    return (sqrt_n*sqrt_n == n);  
}
	
// Based on Lagrange's Four Square theorem, there 
// are only 4 possible results: 1, 2, 3, 4.
public static int perfectSquaresLagrange(int n) 
{  
    // If n is a perfect square, return 1.
    if(is_square(n)) 
    {
        return 1;  
    }

    // The result is 4 if n can be written in the 
    // form of 4^k*(8*m + 7).
    while ((n & 3) == 0) // n%4 == 0  
    {
        n >>= 2;  
    }
    if ((n & 7) == 7) // n%8 == 7
    {
        return 4;
    }

    // Check whether 2 is the result.
    int sqrt_n = (int)(Math.sqrt(n)); 
    for(int i = 1; i <= sqrt_n; i++)
    {  
        if (is_square(n - i*i)) 
        {
            return 2;  
        }
    }  

    return 3;  
}