C++ Exercises: Find the number of perfect square numbers which represent a sum of a given number

C++ Math: Exercise-27 with Solution

Write a C++ program to find the number of perfect square (e.g. 1, 4, 9, 16, ...) numbers which represent a sum of a given number.

Sample Input: n = 5
Number of perfect square whose sum equal to 5 = 2
Sample Input: n = 7
Number of perfect square whose sum equal to 7 = 4

Sample Solution:

C++ Code :

#include <iostream>
#include <vector>

using namespace std;

int numSquares(int n) {
        
        vector<int> table(n + 1, 0);

        for(auto i = 1; i <= n; ++i)
        {
            int value = INT_MAX;
            for(auto j = 1; j * j <= i; ++j)
            {
                value = min(value, table[i - j * j] + 1);
            }

            table[i] = value;
        }

        return table[n];
    }

int main() 
{
    int n = 5;  // (4 + 1)
    cout << "\nNumber of perfect square whose sum equal to " << n << " = " << numSquares(n) << endl;
	n = 7;  // (4 + 1 + 1 + 1)
    cout << "\nNumber of perfect square whose sum equal to " << n << " = " << numSquares(n) << endl;	   	  	  	  	        	        
    n = 12;  // (4 + 4 + 4)
    cout << "\nNumber of perfect square whose sum equal to " << n << " = " << numSquares(n) << endl;
	return 0;
    
}

Sample Output:

Number of perfect square whose sum equal to 5 = 2

Number of perfect square whose sum equal to 7 = 4

Number of perfect square whose sum equal to 12 = 3

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to find the missing number in a given array of integers taken from the sequence 0, 1, 2, 3, ...,n.
Next: Write a C++ program to break a given integer in at least two parts (positive integers) to maximize the product of those integers.