{"id":442,"date":"2023-11-15T08:30:03","date_gmt":"2023-11-15T08:30:03","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=442"},"modified":"2023-11-24T05:59:08","modified_gmt":"2023-11-24T05:59:08","slug":"perfect-squares","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/perfect-squares\/","title":{"rendered":"Perfect Squares Problem (to Add Sum to Given Number)"},"content":{"rendered":"\n<p>Discovering hidden patterns and finding solutions to challenging problems are two fascinating aspects of mathematics and programming. One such important concept is the perfect squares. In this article, we will explore the fascinating problem of finding the least number of perfect squares that sum up to a given number using recursion and dynamic programming.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is a Perfect Squares Problem?<\/strong><\/h2>\n\n\n\n<p> A perfect square is a number that can be expressed as the product of an integer multiplied by itself. <\/p>\n\n\n\n<p><strong>In the Perfect Squares problem, we are given a number n and we have to find the goal to find the minimum number of perfect square numbers (numbers that are squares of integers) whose sum is equal to a given number n.<\/strong><\/p>\n\n\n\n<p>Let us take an example to understand clearly:<\/p>\n\n\n\n<p>Suppose N = 12<\/p>\n\n\n\n<p>12 can be obtained in many ways by adding perfect square numbers but the best way to make 12 by adding a minimum perfect square number is (4+4+4).<\/p>\n\n\n\n<p>12 can be obtained by adding the perfect square number till 3<sup>2<\/sup> because 3<sup>2<\/sup> = 9 (9&lt;12) and 4<sup>2<\/sup> = 16 (16&gt;12) so we cannot add 4<sup>2<\/sup> to make 12<\/p>\n\n\n\n<p>So 12 can only be obtained by using addition on 1<sup>2<\/sup>, 2<sup>2<\/sup>, 3<sup>2<\/sup>.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"509\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-1024x509.png\" alt=\"Example of perfect square problem\" class=\"wp-image-445\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-1024x509.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-300x149.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-768x382.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-360x180.png 360w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-750x373.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3-1140x566.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-3.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\"><strong>Recursive Approach<\/strong><\/h3>\n\n\n\n<p><strong>A recursive approach to solving the perfect squares problem involves defining a recursive function that calculates the minimum number of perfect square numbers needed to sum up to a given number n.<\/strong> The function will have a base case and make recursive calls to smaller subproblems:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will create a function that checks whether n is a perfect square.<br><\/li>\n\n\n\n<li>The function makes recursive calls for each possible perfect square less than or equal to n.<br><\/li>\n\n\n\n<li>The base case checks if n itself is a perfect square. If it is, the function returns 1, indicating that it&#8217;s already a perfect square.<br><\/li>\n\n\n\n<li>The result is updated by choosing the minimum of the current value and the result of the recursive call for the subproblem (n &#8211; i*i).<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"496\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-1024x496.png\" alt=\"Recursive Approach Example\" class=\"wp-image-446\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-1024x496.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-300x145.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-768x372.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-750x363.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3-1140x552.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-3.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>We will further explore and store the minimum in each step and in this case, we will explore 8.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"514\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-1024x514.png\" alt=\"Exploring 8 in example\" class=\"wp-image-447\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-1024x514.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-300x150.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-768x385.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-360x180.png 360w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-750x376.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3-1140x572.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-3.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>The time complexity is exponential because, in the worst case, the function explores all possible perfect squares less than or equal to n, and for each of these squares, it makes a recursive call. The number of possible perfect squares explored is roughly n&nbsp; and the depth of the&nbsp;recursive tree can go up to n therefore the overall time complexity is O(n^n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Dynamic Programming Approach<\/strong><\/h3>\n\n\n\n<p><a href=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\">Dynamic programming<\/a> is a powerful technique that can be applied to solve various optimization problems. In finding the least number of perfect squares, we can utilize dynamic programming to compute the solution efficiently. In this approach,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will create an array, dp[], where dp[i] represents the minimum number of perfect squares required to achieve the sum i.&nbsp;<br><\/li>\n\n\n\n<li>We initialize all elements of dp[] to a maximum value to signify that they are yet to be computed and Initialize the table with base cases. For example, the minimum number of perfect squares needed to sum up to 0 is 0 (no squares needed). The minimum number for 1 is 1, as 1 itself is a perfect square.<br><\/li>\n\n\n\n<li>We will iterate through all numbers from 1 to n and update the dp[] array based on the minimum sum achievable. By considering different combinations of perfect squares,&nbsp;<br><\/li>\n\n\n\n<li>We can gradually build up the solution until we reach the desired number. Finally, we return dp[n] as the minimum number of perfect squares required to sum up to n.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to solve the &#8216;Perfect Squares&#8217; problem using dynamic programming approach:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nclass Solution {\npublic:\n    int numSquares(int n) {\n        \/\/ Create a vector to store the minimum number of perfect squares required for each number up to n.\n        std::vector&lt;int&gt; dp(n + 1, INT_MAX);\n\n        \/\/ Initialize base cases\n        dp[0] = 0;\n        dp[1] = 1;\n\n        \/\/ Build up the dp table\n        for (int i = 2; i &lt;= n; ++i) {\n            for (int j = 1; j * j &lt;= i; ++j) {\n                dp[i] = std::min(dp[i], dp[i - j * j] + 1);\n            }\n        }\n\n        \/\/ Return the result from the last cell of the dp table\n        return dp[n];\n    }\n};\n\nint main() {\n    Solution solution;\n    int n = 12;\n    int result = solution.numSquares(n);\n\n    std::cout &lt;&lt; &quot;The minimum number of perfect squares needed to sum to &quot; &lt;&lt; n &lt;&lt; &quot; is: &quot; &lt;&lt; result &lt;&lt; std::endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>We can also solve the same programming program in Java:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\nclass Solution {\n    public int numSquares(int n) {\n        \/\/ Create an array to store the minimum number of perfect squares required for each number up to n.\n        int[] dp = new int[n + 1];\n        Arrays.fill(dp, Integer.MAX_VALUE);\n\n        \/\/ Initialize base cases\n        dp[0] = 0;\n        dp[1] = 1;\n\n        \/\/ Build up the dp table\n        for (int i = 2; i &lt;= n; ++i) {\n            for (int j = 1; j * j &lt;= i; ++j) {\n                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);\n            }\n        }\n\n        \/\/ Return the result from the last cell of the dp table\n        return dp[n];\n    }\n\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n        int n = 12;\n        int result = solution.numSquares(n);\n        System.out.println(&quot;The minimum number of perfect squares needed to sum to &quot; + n + &quot; is: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>The dynamic programming approach to solve the &#8216;Perfect Squares&#8217; leetcode problem can easily be implemented in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">class Solution:\n    def numSquares(self, n: int) -&gt; int:\n        # Create a list to store the minimum number of perfect squares required for each number up to n.\n        dp = [float('inf')] * (n + 1)\n\n        # Initialize base cases\n        dp[0] = 0\n        dp[1] = 1\n\n        # Build up the dp table\n        for i in range(2, n + 1):\n            j = 1\n            while j * j &lt;= i:\n                dp[i] = min(dp[i], dp[i - j * j] + 1)\n                j += 1\n\n        # Return the result from the last cell of the dp table\n        return dp[n]\n\n# Test the solution\nsolution = Solution()\nn = 12\nresult = solution.numSquares(n)\nprint(f&quot;The minimum number of perfect squares needed to sum to {n} is: {result}&quot;)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The minimum number of perfect squares needed to sum to 12 is: 3<\/code><\/pre>\n\n\n\n<p>The time complexity for this approach is O(n*sqrt n) and the space complexity is O(n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Comparison of Both Approaches<\/strong><\/h3>\n\n\n\n<p>Let\u2019s see a quick review of both the methods:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approach<\/strong><\/td><td><strong>Time Complexity<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>Space Complexity<\/strong><\/td><td><strong>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Details<\/strong><\/td><\/tr><tr><td>Recursive Approach<\/td><td>O(n)<sup>n<\/sup>&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(1)<\/td><td>It explores all possible perfect squares less than or equal to n, and for each of these squares, it makes a recursive call.<\/td><\/tr><tr><td>Dynamic Programming Approach<\/td><td>O(n*sqrt n)<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(n)<\/td><td>The dynamic programming approach uses an array to store the result of the pre-computed problem.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>The dynamic programming approach is recommended for practical implementations, providing a good balance between time and space complexity.<\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>For the perfect square problem, we have discussed two approaches. The <a href=\"https:\/\/favtutor.com\/blogs\/recursion-cpp\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/recursion-cpp\">recursive approach<\/a>, while conceptually straightforward, is not practical for larger inputs due to its exponential time complexity. Dynamic programming approach significantly improves efficiency by using memoization to avoid redundant calculations, resulting in a polynomial time complexity. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand how to solve the leetcode problem of Perfect Square to find minimum perfect squares that sum up to a given number.<\/p>\n","protected":false},"author":12,"featured_media":448,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[25,14,15,43],"class_list":["post-442","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dp","tag-dsa","tag-leetcode","tag-recursion"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=442"}],"version-history":[{"count":11,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/442\/revisions"}],"predecessor-version":[{"id":550,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/442\/revisions\/550"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/448"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}