Minimum number of squares whose sum equals to given number N

Problem: Given number N, find the least number of perfect square number sum needed to get N.

For example:

Input: n = 20
Output: 2

20 = (16 + 4) i.e 2

Input: n = 12
Output: 3

12 = (9 + 1 + 1 + 1) i.e 3

This question can be solved with the basic knowledge of recursion.

Idea is to take a list of perfect square numbers i.e. 1, 4, 9, 16, 25,… and see from which number a minimum jump can be performed. We only need to check till sqrt(N) numbers in above list, since from sqrt(N)th number we can directly jump on N.

Let proceed with an example:

let N=12 , thus we need to traverse only sqrt(12) = 3 numbers i.e. {1, 4, 9} since from 16 onward we can’t reach 12. This thing clearly explains sqrt(N) concept.

Now, to reach 12 we have 3 choices,

1. from (12-1)th state. 11th 
2. from (12-4)th state. 8th 
3. from (12-9)th state. 3rd 

 So, we just take (minimum cost to reach 11th, 8th, 3rd) + 1 as the answer to reach 12th state.

Method 1: One of the method is to use recursion. Following is the implementation:

class practice 
{

    /* method to return required result */
    public static int minNumbers(int n, int sq) 
    {
        
        /* handling base case */
        if (n <= 0) 
        {
            return 0;
        }

        int min = minNumbers(n - 1 * 1, sq);

        /* checking for all numbers from 2 to sqrt(n) */
        for (int i = 2; i <= sq; i++) 
        {
            if (n >= i * i) 
            {
                min = Math.min(min, minNumbers(n - i * i, sq));
            }
        }
        
        return min + 1;
    }

    /* driver method */
    public static void main(String[] args) 
    {
        
        int n = 20;
        int sq = (int) Math.sqrt(n);
        System.out.println(minNumbers(n, sq));

    }
}

Output:

2

Time Complexity: Exponential

Method 2: We need more optimised solution. If we draw the complete recursion tree, we can observer that many sub-problems are solved again and again. For example, when we start from n = 6, we can reach 4 by subtracting one 2 times and by subtracting 2 one times. So the subproblem for 4 is called twice.

Hence we follow a dynamic approach to solve this problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.

Below is Dynamic Programming based solution:

class practice
{
    /* method to return required result */
    static int minNumbers(int n)
    {
        /* dynamic programming table to store sq */
        int dp[] = new int[n+1];
      
        /* table for base case entries */
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
      
        /* filling rest of the table using recursive formula */
        for (int i = 4; i <= n; i++)
        {
            /* max value is i as i can always be represented
               as 1*1 + 1*1 + ... */
            dp[i] = i;
      
            /* go through all smaller numbers to recursively find minimum */
            for (int x = 1; x <= i; x++) {
                int temp = x*x;
                if (temp > i)
                    break;
                else 
                    dp[i] = Math.min(dp[i], 1 + dp[i-temp]);
            }
        }
      
        return dp[n];
    }

    /* driver method */
    public static void main(String args[])
    {
       System.out.println(minNumbers(20));
    }
}

Output:

2

Time Complexity: N*sqrt(N)