Find the minimum number of squares that sum to a given number
Given a positive integer n, find the minimum number of squares that sums to n.
For example,
Output: 1
100 is a perfect square. It can be represented as 102.
Input: 10
Output: 2
10 can be represented as 32 + 12.
Input: 63
Output: 4
63 can be represented as 72 + 32 + 22 + 12.
The idea is to use recursion. For each positive integer i <= √n, recur for n-i2 and find the minimum number of squares that sum to n. This is demonstrated below in C++ and Java:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <cmath> using namespace std; // Utility function to check if a given number `n` is a perfect square or not bool isPerfectSquare(int n) { // find the floating-point value of the square root of `n` long double sqr = sqrt(n); // return true if the square root is an integer return sqr == floor(sqr); } // Recursive function to find the minimum number of squares that sum to `n` int findMinSquares(int n) { // base case: `n` is a perfect square if (isPerfectSquare(n)) { return 1; } // initialize the result with the maximum number of squares possible int result = n; // loop through all positive integers less than the square root of `n` for (int i = 1; i*i < n; i++) { // recur for `n-i×i` and update the result if a lesser value is found result = min(result, 1 + findMinSquares(n - i*i)); } return result; } int main() { int n = 63; cout << "The minimum number of squares is " << findMinSquares(n) << endl; return 0; } |
Output:
The minimum number of squares is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Main { // Utility function to check if a given number `n` is a perfect square or not public static boolean isPerfectSquare(int n) { // find the floating-point value of the square root of `n` double sqr = Math.sqrt(n); // return true if the square root is an integer return sqr == Math.floor(sqr); } // Recursive function to find the minimum number of squares that sum to `n` public static int findMinSquares(int n) { // base case: `n` is a perfect square if (isPerfectSquare(n)) { return 1; } // initialize the result with the maximum number of squares possible int result = n; // loop through all positive integers less than the square root of `n` for (int i = 1; i*i < n; i++) { // recur for `n-i×i` and update the result if a lesser value is found result = Integer.min(result, 1 + findMinSquares(n - i*i)); } return result; } public static void main(String[] args) { int n = 63; System.out.println("The minimum number of squares is " + findMinSquares(n)); } } |
Output:
The minimum number of squares is 4
The time complexity of the above solution is exponential and requires additional space for the recursion (call stack). The problem can be recursively broken down into smaller subproblems, and each subproblem gets repeated several times. The repeated subproblems can be easily seen by drawing a recursion tree.
Since the problem satisfies optimal substructure and overlapping subproblems properties of dynamic programming, the subproblem solution can be derived in a bottom-up manner. Following is the dynamic programming solution in C, Java, and Python, where an auxiliary array is used to store solutions to the smaller subproblems:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <stdio.h> // Utility function to find the minimum among two integers `x` and `y` int min(int x, int y) { return x < y ? x : y; } // Iterative function to find the minimum number of squares that sum to `n` int findMinSquares(int n) { // create an auxiliary array T[], where T[i] stores the minimum number // of squares that sum to `i` int T[n + 1]; // fill the auxiliary array T[] in a bottom-up manner for (int i = 0; i <= n; i++) { // initialize T[i] with the maximum number of squares possible T[i] = i; // loop through all positive integers less than or equal to the // square root of `i` for (int j = 1; j*j <= i; j++) { // calculate the value of T[i] using the result of a smaller // subproblem T[i-j×j] T[i] = min(T[i], 1 + T[i - j*j]); } } return T[n]; } int main(void) { int n = 63; printf("The minimum number of squares is %d", findMinSquares(n)); return 0; } |
Output:
The minimum number of squares is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Main { // Iterative function to find the minimum number of squares that sum to `n` public static int findMinSquares(int n) { // create an auxiliary array T[], where T[i] stores the minimum number // of squares that sum to `i` int[] T = new int[n + 1]; // fill the auxiliary array T[] in a bottom-up manner for (int i = 0; i <= n; i++) { // initialize T[i] with the maximum number of squares possible T[i] = i; // loop through all positive integers less than or equal to the // square root of `i` for (int j = 1; j*j <= i; j++) { // calculate the value of T[i] using the result of a smaller // subproblem T[i-j×j] T[i] = Integer.min(T[i], 1 + T[i - j*j]); } } return T[n]; } public static void main(String[] args) { int n = 63; System.out.println("The minimum number of squares is " + findMinSquares(n)); } } |
Output:
The minimum number of squares is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# Iterative function to find the minimum number of squares that sum to `n` def findMinSquares(n): # create an auxiliary array T[], where T[i] stores the minimum number # of squares that sum to `i` T = [0] * (n + 1) # fill the auxiliary array T[] in a bottom-up manner for i in range(n + 1): # initialize T[i] with the maximum number of squares possible T[i] = i # loop through all positive integers less than or equal to the # square root of `i` j = 1 while j*j <= i: # calculate the value of T[i] using the result of a smaller # subproblem T[i-j×j] T[i] = min(T[i], 1 + T[i - j*j]) j += 1 return T[n] if __name__ == '__main__': n = 63 print('The minimum number of squares is', findMinSquares(n)) |
Output:
The minimum number of squares is 4
The time complexity of the above solution is O(n.√n), and the extra space used by the program is O(n).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)