A number can always be represented as a sum of squares of other numbers. Note that 1 is a square and we can always break a number as (1*1 + 1*1 + 1*1 + …). Given a number n, find the minimum number of squares that sum to X.
Examples :
Input: n = 100
Output: 1
Explanation:
100 can be written as 102. Note that 100 can also be written as 52 + 52 + 52 + 52, but this representation requires 4 squares.Input: n = 6
Output: 3
The idea is simple, we start from 1 and go to a number whose square is smaller than or equals n. For every number x, we recur for n-x. Below is the recursive formula.
If n = 1 and x*x <= n
Below is a simple recursive solution based on the above recursive formula.
C++
// A naive recursive C++ // program to find minimum// number of squares whose sum // is equal to a given number#include <bits/stdc++.h>using namespace std;// Returns count of minimum // squares that sum to nint getMinSquares(unsigned int n){ // base cases // if n is perfect square then // Minimum squares required is 1 // (144 = 12^2) if (sqrt(n) - floor(sqrt(n)) == 0) return 1; if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required // is n (1*1 + 1*1 + ..) int res = n; // Go through all smaller numbers // to recursively find minimum for (int x = 1; x <= n; x++) { int temp = x * x; if (temp > n) break; else res = min(res, 1 + getMinSquares (n - temp)); } return res;}// Driver codeint main(){ cout << getMinSquares(6); return 0;} |
Java
// A naive recursive JAVA // program to find minimum// number of squares whose // sum is equal to a given numberimport java.util.*;import java.io.*;class squares { // Returns count of minimum // squares that sum to n static int getMinSquares(int n) { // base cases if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is int res = n; // n (1*1 + 1*1 + ..) // Go through all smaller numbers // to recursively find minimum for (int x = 1; x <= n; x++) { int temp = x * x; if (temp > n) break; else res = Math.min(res, 1 + getMinSquares(n - temp)); } return res; } // Driver code public static void main(String args[]) { System.out.println(getMinSquares(6)); }}/* This code is contributed by Rajat Mishra */ |
Python3
# A naive recursive Python program to# find minimum number of squares whose# sum is equal to a given number# Returns count of minimum squares # that sum to ndef getMinSquares(n): # base cases if n <= 3: return n; # getMinSquares rest of the table # using recursive formula # Maximum squares required # is n (1 * 1 + 1 * 1 + ..) res = n # Go through all smaller numbers # to recursively find minimum for x in range(1, n + 1): temp = x * x; if temp > n: break else: res = min(res, 1 + getMinSquares(n - temp)) return res;# Driver code print(getMinSquares(6))# This code is contributed by nuclode |
C#
// A naive recursive C# program// to find minimum number of// squares whose sum is equal// to a given numberusing System;class GFG { // Returns count of minimum // squares that sum to n static int getMinSquares(int n) { // base cases if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is // n (1*1 + 1*1 + ..) int res = n; // Go through all smaller numbers // to recursively find minimum for (int x = 1; x <= n; x++) { int temp = x * x; if (temp > n) break; else res = Math.Min(res, 1 + getMinSquares(n - temp)); } return res; } // Driver Code public static void Main() { Console.Write(getMinSquares(6)); }}// This code is contributed by nitin mittal |
Javascript
<script>// A naive recursive Javascript program// to find minimum number of squares // whose sum is equal to a given number// Returns count of minimum// squares that sum to nfunction getMinSquares(n){ // base cases if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is // n (1*1 + 1*1 + ..) let res = n; // Go through all smaller numbers // to recursively find minimum for(let x = 1; x <= n; x++) { let temp = x * x; if (temp > n) break; else res = Math.min(res, 1 + getMinSquares(n - temp)); } return res;}// Driver codedocument.write(getMinSquares(6));// This code is contributed by suresh07</script> |
PHP
<?php// A naive recursive PHP program// to find minimum number of // squares whose sum is equal // to a given number// Returns count of minimum // squares that sum to nfunction getMinSquares($n){ // base cases if ($n <= 3) return $n; // getMinSquares rest of the // table using recursive formula // Maximum squares required // is n (1*1 + 1*1 + ..) $res = $n; // Go through all smaller numbers // to recursively find minimum for ($x = 1; $x <= $n; $x++) { $temp = $x * $x; if ($temp > $n) break; else $res = min($res, 1 + getMinSquares($n - $temp)); } return $res;}// Driver Codeecho getMinSquares(6);// This code is contributed// by nitin mittal.?> |
Output
3
Time Complexity: O(2^n)
Space Complexity: O(n) where n is the recursion stack space.
The time complexity of the above solution is exponential. If we draw the recursion tree, we can observe that many subproblems 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.
Since the same subproblems are called again, this problem has the Overlapping Subproblems property. So min square sum problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of the same subproblems can be avoided by constructing a temporary array table[][] in a bottom-up manner. Below is a Dynamic programming-based solution.
C++
// A dynamic programming based // C++ program to find minimum// number of squares whose sum // is equal to a given number#include <bits/stdc++.h>using namespace std;// Returns count of minimum // squares that sum to nint getMinSquares(int n){ // We need to check base case // for n i.e. 0,1,2 // the below array creation // will go OutOfBounds. if(n<=3) return n; // Create a dynamic // programming table // to store sq int* dp = new int[n + 1]; // getMinSquares table // for base case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares 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 // to recursively find minimum for (int x = 1; x <= ceil(sqrt(i)); x++) { int temp = x * x; if (temp > i) break; else dp[i] = min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; delete[] dp; return res;}// Driver codeint main(){ cout << getMinSquares(6); return 0;} |
Java
// A dynamic programming based // JAVA program to find minimum// number of squares whose sum // is equal to a given numberimport java.util.*;import java.io.*;class squares { // Returns count of minimum // squares that sum to n static int getMinSquares(int n) { // We need to add a check // here for n. If user enters // 0 or 1 or 2 // the below array creation // will go OutOfBounds. if (n <= 3) return n; // Create a dynamic programming // table // to store sq int dp[] = new int[n + 1]; // getMinSquares table for // base case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares 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 // to recursively find minimum for (int x = 1; x <= Math.ceil( Math.sqrt(i)); x++) { int temp = x * x; if (temp > i) break; else dp[i] = Math.min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; return res; } // Driver Code public static void main(String args[]) { System.out.println(getMinSquares(6)); }} /* This code is contributed by Rajat Mishra */ |
Python3
# A dynamic programming based Python# program to find minimum number of# squares whose sum is equal to a # given numberfrom math import ceil, sqrt# Returns count of minimum squares # that sum to ndef getMinSquares(n): # Create a dynamic programming table # to store sq and getMinSquares table # for base case entries dp = [0, 1, 2, 3] # getMinSquares rest of the table # using recursive formula for i in range(4, n + 1): # max value is i as i can always # be represented as 1 * 1 + 1 * 1 + ... dp.append(i) # Go through all smaller numbers # to recursively find minimum for x in range(1, int(ceil(sqrt(i))) + 1): temp = x * x; if temp > i: break else: dp[i] = min(dp[i], 1 + dp[i-temp]) # Store result return dp[n]# Driver codeprint(getMinSquares(6))# This code is contributed by nuclode |
C#
// A dynamic programming based// C# program to find minimum// number of squares whose sum// is equal to a given numberusing System;class squares { // Returns count of minimum // squares that sum to n static int getMinSquares(int n) { // We need to add a check here // for n. If user enters 0 or 1 or 2 // the below array creation will go // OutOfBounds. if (n <= 3) return n; // Create a dynamic programming // table to store sq int[] dp = new int[n + 1]; // getMinSquares table for base // case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares for 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 // to recursively find minimum for (int x = 1; x <= Math.Ceiling( Math.Sqrt(i)); x++) { int temp = x * x; if (temp > i) break; else dp[i] = Math.Min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; return res; } // Driver Code public static void Main(String[] args) { Console.Write(getMinSquares(6)); }}// This code is contributed by Nitin Mittal. |
Javascript
<script>// A dynamic programming based// javascript program to find minimum// number of squares whose sum// is equal to a given number // Returns count of minimum // squares that sum to n function getMinSquares( n) { // We need to add a check here // for n. If user enters 0 or 1 or 2 // the below array creation will go // OutOfBounds. if (n <= 3) return n; // Create a dynamic programming // table to store sq var dp = new Array(n + 1); // getMinSquares table for base // case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares for rest of the // table using recursive formula for (var 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 // to recursively find minimum for (var x = 1; x <= Math.ceil( Math.sqrt(i)); x++) { var temp = x * x; if (temp > i) break; else dp[i] = Math.min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] var res = dp[n]; return res; } // Driver Code document.write(getMinSquares(6));</script> |
PHP
<?php// A dynamic programming based // PHP program to find minimum// number of squares whose sum// is equal to a given number// Returns count of minimum// squares that sum to nfunction getMinSquares($n){ // Create a dynamic programming // table to store sq $dp; // getMinSquares table for // base case entries $dp[0] = 0; $dp[1] = 1; $dp[2] = 2; $dp[3] = 3; // getMinSquares rest of the // table using recursive formula for ($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 ($x = 1; $x <= ceil(sqrt($i)); $x++) { $temp = $x * $x; if ($temp > $i) break; else $dp[$i] = min($dp[$i], (1 + $dp[$i - $temp])); } } // Store result // and free dp[] $res = $dp[$n]; // delete $dp; return $res;}// Driver Codeecho getMinSquares(6); // This code is contributed// by shiv_bhakt. ?> |
Output
3
Time Complexity: O(n*sqrtn)
Auxiliary Space: O(n)
Thanks to Gaurav Ahirwar for suggesting this solution.
Another Approach: (USING MEMOIZATION)
The problem can be solved using the memoization method (dynamic programming) as well.
Below is the implementation:
C++
#include <bits/stdc++.h>using namespace std;int minCount(int n){ int* minSquaresRequired = new int[n + 1]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for (int i = 2; i <= n; ++i) { minSquaresRequired[i] = INT_MAX; for (int j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } int result = minSquaresRequired[n]; delete[] minSquaresRequired; return result;}// Driver codeint main(){ cout << minCount(6); return 0;} |
Java
import java.util.*;class GFG { static int minCount(int n) { int[] minSquaresRequired = new int[n + 1]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for (int i = 2; i <= n; ++i) { minSquaresRequired[i] = Integer.MAX_VALUE; for (int j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = Math.min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } int result = minSquaresRequired[n]; return result; } // Driver code public static void main(String[] args) { System.out.print(minCount(6)); }}// This code contributed by gauravrajput1 |
Python3
import sysdef minCount(n): minSquaresRequired = [0 for i in range(n+1)]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for i in range(2,n+1): minSquaresRequired[i] = sys.maxsize; j = 1 for j in range(1,i - (j * j)): if(i - (j * j) >= 0): minSquaresRequired[i] = min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); else: break minSquaresRequired[i] += 1; result = minSquaresRequired[n]; return result;# Driver codeif __name__ == '__main__': print(minCount(6));# This code is contributed by umadevi9616 |
C#
using System;class GFG { static int minCount(int n) { int[] minSquaresRequired = new int[n + 1]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for (int i = 2; i <= n; ++i) { minSquaresRequired[i] = Int32.MaxValue; for (int j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = Math.Min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } int result = minSquaresRequired[n]; return result; } // Driver code public static void Main(String[] args) { Console.Write(minCount(6)); }}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach function minCount(n) { let minSquaresRequired = new Array(n + 1); minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for (let i = 2; i <= n; ++i) { minSquaresRequired[i] = Number.MAX_VALUE; for (let j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = Math.min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } let result = minSquaresRequired[n]; return result; } // Driver code document.write(minCount(6));// This code is contributed by Potta Lokesh </script> |
Output
3
Another Approach:
This problem can also be solved by using graphs. Here is the basic idea of how it can be done.
We will use BFS (Breadth-First Search) to find the minimum number of steps from a given value of n to 0.
So, for every node, we will push the next possible valid path which is not visited yet into a queue and,
and if it reaches node 0, we will update our answer if it is less than the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum // squares that sum to n int numSquares(int n) { // Creating visited vector // of size n + 1 vector<int> visited(n + 1,0); // Queue of pair to store node // and number of steps queue< pair<int,int> >q; // Initially ans variable is // initialized with inf int ans = INT_MAX; // Push starting node with 0 // 0 indicate current number // of step to reach n q.push({n,0}); // Mark starting node visited visited[n] = 1; while(!q.empty()) { pair<int,int> p; p = q.front(); q.pop(); // If node reaches its destination // 0 update it with answer if(p.first == 0) ans=min(ans, p.second); // Loop for all possible path from // 1 to i*i <= current node(p.first) for(int i = 1; i * i <= p.first; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path=(p.first - (i*i)); // Check if it is valid and // not visited yet if(path >= 0 && ( !visited[path] || path == 0)) { // Mark visited visited[path]=1; // Push it it Queue q.push({path,p.second + 1}); } } } // Return ans to calling function return ans; }// Driver codeint main() { cout << numSquares(12); return 0; } |
Java
// Java program for the above approachimport java.util.*;import java.awt.Point;class GFG{ // Function to count minimum // squares that sum to n public static int numSquares(int n) { // Creating visited vector // of size n + 1 int visited[] = new int[n + 1]; // Queue of pair to store node // and number of steps Queue<Point> q = new LinkedList<>(); // Initially ans variable is // initialized with inf int ans = Integer.MAX_VALUE; // Push starting node with 0 // 0 indicate current number // of step to reach n q.add(new Point(n, 0)); // Mark starting node visited visited[n] = 1; while(q.size() != 0) { Point p = q.peek(); q.poll(); // If node reaches its destination // 0 update it with answer if(p.x == 0) ans = Math.min(ans, p.y); // Loop for all possible path from // 1 to i*i <= current node(p.first) for(int i = 1; i * i <= p.x; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path = (p.x - (i * i)); // Check if it is valid and // not visited yet if(path >= 0 && (visited[path] == 0 || path == 0)) { // Mark visited visited[path] = 1; // Push it it Queue q.add(new Point(path, p.y + 1)); } } } // Return ans to calling function return ans; } // Driver code public static void main(String[] args) { System.out.println(numSquares(12)); }}// This code is contributed by divyesh072019 |
Python3
# Python3 program for the above approach import sys# Function to count minimum # squares that sum to n def numSquares(n) : # Creating visited vector # of size n + 1 visited = [0]*(n + 1) # Queue of pair to store node # and number of steps q = [] # Initially ans variable is # initialized with inf ans = sys.maxsize # Push starting node with 0 # 0 indicate current number # of step to reach n q.append([n, 0]) # Mark starting node visited visited[n] = 1 while(len(q) > 0) : p = q[0] q.pop(0) # If node reaches its destination # 0 update it with answer if(p[0] == 0) : ans = min(ans, p[1]) # Loop for all possible path from # 1 to i*i <= current node(p.first) i = 1 while i * i <= p[0] : # If we are standing at some node # then next node it can jump to will # be current node- # (some square less than or equal n) path = p[0] - i * i # Check if it is valid and # not visited yet if path >= 0 and (visited[path] == 0 or path == 0) : # Mark visited visited[path] = 1 # Push it it Queue q.append([path,p[1] + 1]) i += 1 # Return ans to calling function return ansprint(numSquares(12))# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ public class Point{ public int x, y; public Point(int x, int y) { this.x = x; this.y = y; }}// Function to count minimum // squares that sum to n public static int numSquares(int n) { // Creating visited vector // of size n + 1 int []visited = new int[n + 1]; // Queue of pair to store node // and number of steps Queue q = new Queue(); // Initially ans variable is // initialized with inf int ans = 1000000000; // Push starting node with 0 // 0 indicate current number // of step to reach n q.Enqueue(new Point(n, 0)); // Mark starting node visited visited[n] = 1; while(q.Count != 0) { Point p = (Point)q.Dequeue(); // If node reaches its destination // 0 update it with answer if (p.x == 0) ans = Math.Min(ans, p.y); // Loop for all possible path from // 1 to i*i <= current node(p.first) for(int i = 1; i * i <= p.x; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path = (p.x - (i * i)); // Check if it is valid and // not visited yet if (path >= 0 && (visited[path] == 0 || path == 0)) { // Mark visited visited[path] = 1; // Push it it Queue q.Enqueue(new Point(path, p.y + 1)); } } } // Return ans to calling function return ans; }// Driver codepublic static void Main(string[] args){ Console.Write(numSquares(12));}}// This code is contributed by rutvik_56 |
Javascript
// JavaScript program for the above approach // Function to count minimum // squares that sum to n function numSquares(n) { // Creating visited vector // of size n + 1 let visited = new Array(n + 1).fill(0); // Queue of pair to store node // and number of steps let q = []; // Initially ans variable is // initialized with inf let ans = Number.MAX_SAFE_INTEGER; // Push starting node with 0 // 0 indicate current number // of step to reach n q.push([n, 0]); // Mark starting node visited visited[n] = 1; while(q.length > 0) { let p = q[0]; q.shift(); // If node reaches its destination // 0 update it with answer if(p[0] == 0) ans = Math.min(ans, p[1]); // Loop for all possible path from // 1 to i*i <= current node(p.first) let i = 1; while (i * i <= p[0]) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) let path = p[0] - i * i; // Check if it is valid and // not visited yet if (path >= 0 && (visited[path] == 0 || path == 0) ) { // Mark visited visited[path] = 1; // Push it it Queue q.push([path,p[1] + 1]); } i += 1; } } // Return ans to calling function return ans;}console.log(numSquares(12));// This code is contributed by phasing17 |
Output
3
The time complexity of the above problem is O(n)*sqrt(n) which is better than the Recursive approach.
Also, it is a great way to understand how BFS (Breadth-First Search) works.
Please write a if you find anything incorrect, or you want to share more information about the topic discussed above.
Another Approach:
This problem can also be solved using Dynamic programming (Bottom-up approach). The idea is like coin change 2 (in which we need to tell minimum number of coins to make an amount from given coins[] array), here an array of all perfect squares less than or equal to n can be replaced by coins[] array and amount can be replaced by n. Just see this as an unbounded knapsack problem, Let’s see an example:
For given input n = 6, we will make an array upto 4, arr : [1,4]
Here, answer will be (4 + 1 + 1 = 6) i.e. 3.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum // squares that sum to n int numSquares(int n) { //Making the array of perfect squares less than or equal to n vector <int> arr; int i = 1; while(i*i <= n){ arr.push_back(i*i); i++; } //A dp array which will store minimum number of perfect squares //required to make n from i at i th index vector <int> dp(n+1, INT_MAX); dp[n] = 0; for(int i = n-1; i>=0; i--){ //checking from i th value to n value minimum perfect squares required for(int j = 0; j<arr.size(); j++){ //check if index doesn't goes out of bound if(i + arr[j] <= n){ dp[i] = min(dp[i], dp[i+arr[j]]); } } //from current to go to min step one i we need to take one step dp[i]++; } return dp[0]; }// Driver codeint main() { cout << numSquares(12); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to count minimum // squares that sum to n static int numSquares(int n) { // Making the array of perfect squares less than or equal to n Vector <Integer> arr = new Vector<>(); int k = 1; while(k * k <= n){ arr.add(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index int []dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n] = 0; for(int i = n - 1; i >= 0; i--) { // checking from i th value to n value minimum perfect squares required for(int j = 0; j < arr.size(); j++) { // check if index doesn't goes out of bound if(i + arr.elementAt(j) <= n) { dp[i] = Math.min(dp[i], dp[i+arr.elementAt(j)]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[0];}// Driver codepublic static void main(String[] args) { System.out.print(numSquares(12));}} // This code is contributed by umadevi9616. |
Python3
# Python program for the above approach import sys# Function to count minimum# squares that sum to ndef numSquares(n): # Making the array of perfect squares less than or equal to n arr = []; k = 1; while (k * k <= n): arr.append(k * k); k += 1; # A dp array which will store minimum number of perfect squares # required to make n from i at i th index dp = [sys.maxsize for i in range(n+1)]; dp[n] = 0; for i in range(n-1, -1,-1): # checking from i th value to n value minimum perfect squares required for j in range(len(arr)): # check if index doesn't goes out of bound if (i + arr[j] <= n): dp[i] = min(dp[i], dp[i + arr[j]]); # from current to go to min step one i we need to take one step dp[i] += 1; return dp[0];# Driver codeif __name__ == '__main__': print(numSquares(12));# This code is contributed by gauravrajput1 |
C#
// C# program for the above approach using System;using System.Collections.Generic;public class GFG{ // Function to count minimum // squares that sum to n static int numSquares(int n) { // Making the array of perfect squares less than or equal to n List <int> arr = new List<int>(); int k = 1; while(k * k <= n){ arr.Add(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index int []dp = new int[n + 1]; for(int i = 0; i < n + 1; i++) dp[i] = int.MaxValue; dp[n] = 0; for(int i = n - 1; i >= 0; i--) { // checking from i th value to n value minimum perfect squares required for(int j = 0; j < arr.Count; j++) { // check if index doesn't goes out of bound if(i + arr[j] <= n) { dp[i] = Math.Min(dp[i], dp[i+arr[j]]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[0];}// Driver codepublic static void Main(String[] args) { Console.Write(numSquares(12));}} // This code is contributed by umadevi9616 |
Javascript
<script>// javascript program for the above approach // Function to count minimum // squares that sum to n function numSquares(n) { // Making the array of perfect squares less than or equal to n var arr = new Array(); var k = 1; while (k * k <= n) { arr.push(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index var dp = Array(n + 1).fill(Number.MAX_VALUE); dp[n] = 0; for (i = n - 1; i >= 0; i--) { // checking from i th value to n value minimum perfect squares required for (j = 0; j < arr.length; j++) { // check if index doesn't goes out of bound if (i + arr[j] <= n) { dp[i] = Math.min(dp[i], dp[i + arr[j]]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[0]; } // Driver code document.write(numSquares(12));// This code is contributed by umadevi9616</script> |
Output
3
The time complexity of the above problem is O(n)*sqrt(n) as array will be made in sqrt(n) time and for loops for filling dp array will take n*sqrt(n) time atmost. The size of dp array will be n, so space complexity of this approach is O(n).
Another Approach: (Using Mathematics)
The solution is based on Lagrange’s Four Square Theorem.
According to the theorem, there can be atmost 4 solutions to the problem, i.e. 1, 2, 3, 4
Case 1:
Ans = 1 => This can happen if the number is a square number.
n = {a2 : a ∈ W}
Example : 1, 4, 9, etc.
Case 2:
Ans = 2 => This is possible if the number is the sum of 2 square numbers.
n = {a2 + b2 : a, b ∈ W}
Example : 2, 5, 18, etc.
Case 3:
Ans = 3 => This can happen if the number is not of the form 4k(8m + 7).
For more information on this : https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
n = {a2 + b2 + c2 : a, b, c ∈ W} ⟷ n ≢ {4k(8m + 7) : k, m ∈ W }
Example : 6, 11, 12 etc.
Case 4:
Ans = 4 => This can happen if the number is of the form 4k(8m + 7).
n = {a2 + b2 + c2 + d2 : a, b, c, d ∈ W} ⟷ n ≡ {4k(8m + 7) : k, m ∈ W }
Example : 7, 15, 23 etc.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// returns true if the input number x is a square number,// else returns falsebool isSquare(int x){ int sqRoot = sqrt(x); return (sqRoot * sqRoot == x);}// Function to count minimum squares that sum to nint cntSquares(int n){ // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for (int i = 1; i <= (int)sqrt(n)+1; i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3;}// Driver Codeint main(){ cout << cntSquares(12) << endl; return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{// returns true if the input number x is a square number,// else returns falsestatic boolean isSquare(int x){ int sqRoot = (int)Math.sqrt(x); return (sqRoot * sqRoot == x);}// Function to count minimum squares that sum to nstatic int cntSquares(int n){ // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for (int i = 1; i <= (int)Math.sqrt(n)+1; i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3;}// Driver Codepublic static void main(String[] args){ System.out.print(cntSquares(12) +"\n");}}// This code is contributed by umadevi9616 |
Python3
# Python code for the above approachimport math# returns True if the input number x is a square number,# else returns Falsedef isSquare(x): sqRoot = int(math.sqrt(x)); return (sqRoot * sqRoot == x);# Function to count minimum squares that sum to ndef cntSquares(n): # ans = 1 if the number is a perfect square if (isSquare(n)): return 1; # ans = 2: # we check for each i if n - (i * i) is a perfect # square for i in range(1, int(math.sqrt(n))+1): if (isSquare(n - (i * i))): return 2; # ans = 4 # possible if the number is representable in the form # 4^a (8*b + 7). while (n % 4 == 0): n >>= 2; if (n % 8 == 7): return 4; # since all the other cases have been evaluated, the # answer can only then be 3 if the program reaches here return 3;# Driver Codeif __name__ == '__main__': print(cntSquares(12) , "");# This code is contributed by gauravrajput1 |
C#
// C# code for the above approachusing System;public class GFG{// returns true if the input number x is a square number,// else returns falsestatic bool isSquare(int x){ int sqRoot = (int)Math.Sqrt(x); return (sqRoot * sqRoot == x);}// Function to count minimum squares that sum to nstatic int cntSquares(int n){ // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for (int i = 1; i <= (int)Math.Sqrt(n)+1; i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3;}// Driver Codepublic static void Main(String[] args){ Console.Write(cntSquares(12) +"\n");}}// This code contributed by umadevi9616 |
Javascript
<script>// javascript code for the above approach // returns true if the input number x is a square number, // else returns false function isSquare(x) { var sqRoot = parseInt( Math.sqrt(x)); return (sqRoot * sqRoot == x); } // Function to count minimum squares that sum to n function cntSquares(n) { // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for (var i = 1; i <= parseInt( Math.sqrt(n))+1; i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3; } // Driver Code document.write(cntSquares(12) + "\n");// This code is contributed by umadevi9616</script> |
Output
3
Time Complexity: O(sqrtn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
