Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

Minimum number of squares whose sum equals to given number n

How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [2]:
project_name = "Minimum Square Sum" 
In [3]:
!pip install jovian --upgrade --quiet
In [4]:
import jovian
In [5]:
jovian.commit(project=project_name)
[jovian] Detected Colab notebook... [jovian] Please enter your API key ( from https://jovian.ai/ ): API KEY: ·········· [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aditya-pat10/minimum-square-sum

Problem Statement

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 + …). Given a non negative number n, find the minimum number of squares that sum to X.

Source: GeeksForGeeks - https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/

The Method

Here's the systematic strategy we'll apply for solving problems:

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

Solution

Problem

A non negative integer number is given. We have to find the minimum number of squares it requires for the sum of those squares equals to the given number n


Input

  1. n - a non negative integer number.

Output

  1. minimum - Minimum number of squares required such that the sum of these squares equals to the given number n.

Based on the above, we can now create a signature of our function:

In [6]:
# Create a function signature here.

def minimum_square_sum(n) :
  pass

Save and upload your work before continuing.

In [7]:
import jovian
In [8]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aditya-pat10/minimum-square-sum

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. Any number.
  2. A large number.
  3. Zero.
  4. One.
  5. A floating point or negative number.

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [92]:
test = {
    'input': { 
        'n' : 11
    },
    'output': 3
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [93]:
tests1 = []
In [94]:
tests1.append(test)
In [95]:
tests1.append({
    'input': {
        'n' : 6 
    },
    'output': 3
})
In [96]:
tests1.append({
    'input': {
        'n' : 27 
    },
    'output': 3
})

tests1.append({
    'input': {
        'n' : 25
    },
    'output': 1
})

tests1.append({
    'input': {
        'n' : 0 
    },
    'output': 1
})

tests1.append({
    'input': {
        'n' : 1 
    },
    'output': 1
})

tests1.append({
    'input': {
        'n' : 21.4 
    },
    'output': -1  #Error
})

tests1.append({
    'input': {
        'n' : -71 
    },
    'output': -1  #Error
})


In [97]:
print(tests1)
[{'input': {'n': 11}, 'output': 3}, {'input': {'n': 6}, 'output': 3}, {'input': {'n': 27}, 'output': 3}, {'input': {'n': 25}, 'output': 1}, {'input': {'n': 0}, 'output': 1}, {'input': {'n': 1}, 'output': 1}, {'input': {'n': 21.4}, 'output': -1}, {'input': {'n': -71}, 'output': -1}]

3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

  1. If n is not a non negative integer, return -1
  2. Set minimum to 1
  3. check for reversed numbers in range (1,n+1).
  4. If the square of number is greater than n, do nothing.
  5. If the square of number is less than n, set n to difference between n and square of the current number and set minimum = (1 + use recursion).
  6. If the square of number is equal to n, return minimum.
  7. Return minimum.

Let's save and upload our work before continuing.

In [98]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aditya-pat10/minimum-square-sum

4. Implement the solution and test it using example inputs. Fix bugs, if any.

In [99]:
def minimum_square_sum(n) :
  temp = -1
  minimum = n
  if n==0:
    return 1
  if n< 0 or type(n) == float:
    return temp
  for i in (range(1,n+1)):
    if i * i == n:
      return 1
      break
    else:
      if i*i > n:
        break
      else:
        temp = n- (i*i)
        minimum = min(minimum, 1 + minimum_square_sum(temp))
  return minimum
In [100]:
print(memo)
{(1, 11): 11, (2, 11): 11, (3, 11): 11, (4, 11): 11, (5, 11): 11, (6, 11): 11, (7, 11): 11, (8, 11): 11, (9, 11): 11, (10, 11): 11, (11, 11): 11, (1, 6): 6, (2, 6): 6, (3, 6): 6, (4, 6): 6, (5, 6): 6, (6, 6): 6, (1, 27): 27, (2, 27): 27, (3, 27): 27, (4, 27): 27, (5, 27): 27, (6, 27): 27, (7, 27): 27, (8, 27): 27, (9, 27): 27, (10, 27): 27, (11, 27): 27, (12, 27): 27, (13, 27): 27, (14, 27): 27, (15, 27): 27, (16, 27): 27, (17, 27): 27, (18, 27): 27, (19, 27): 27, (20, 27): 27, (21, 27): 27, (22, 27): 27, (23, 27): 27, (24, 27): 27, (25, 27): 27, (26, 27): 27, (27, 27): 27, (1, 25): 25, (2, 25): 25, (3, 25): 25, (4, 25): 25, (5, 25): 25, (6, 25): 25, (7, 25): 25, (8, 25): 25, (9, 25): 25, (10, 25): 25, (11, 25): 25, (12, 25): 25, (13, 25): 25, (14, 25): 25, (15, 25): 25, (16, 25): 25, (17, 25): 25, (18, 25): 25, (19, 25): 25, (20, 25): 25, (21, 25): 25, (22, 25): 25, (23, 25): 25, (24, 25): 25, (25, 25): 25, (1, 1): 1}

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [101]:
from jovian.pythondsa import evaluate_test_cases
In [102]:
evaluate_test_cases(minimum_square_sum, tests1)
TEST CASE #0 Input: {'n': 11} Expected Output: 3 Actual Output: 3 Execution Time: 0.07 ms Test Result: PASSED TEST CASE #1 Input: {'n': 6} Expected Output: 3 Actual Output: 3 Execution Time: 0.02 ms Test Result: PASSED TEST CASE #2 Input: {'n': 27} Expected Output: 3 Actual Output: 3 Execution Time: 14.023 ms Test Result: PASSED TEST CASE #3 Input: {'n': 25} Expected Output: 1 Actual Output: 1 Execution Time: 11.385 ms Test Result: PASSED TEST CASE #4 Input: {'n': 0} Expected Output: 1 Actual Output: 1 Execution Time: 0.002 ms Test Result: PASSED TEST CASE #5 Input: {'n': 1} Expected Output: 1 Actual Output: 1 Execution Time: 0.004 ms Test Result: PASSED TEST CASE #6 Input: {'n': 21.4} Expected Output: -1 Actual Output: -1 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #7 Input: {'n': -71} Expected Output: -1 Actual Output: -1 Execution Time: 0.002 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[102]:
[(3, True, 0.07),
 (3, True, 0.02),
 (3, True, 14.023),
 (1, True, 11.385),
 (1, True, 0.002),
 (1, True, 0.004),
 (-1, True, 0.003),
 (-1, True, 0.002)]

Verify that all the test cases were evaluated.

Let's save our work before continuing.

In [103]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aditya-pat10/minimum-square-sum

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

As we have used recursion, it takes exponential time to get the output. In case of the large number test case, we can see it took 100x time to compute the output. If the number is even larger, it would take a massive amount of time for computing.

The additional space required for the algorithm is O(1)

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

In [104]:
from math import ceil, sqrt

def get_square_sum_dp(n):
    if n==0:
      return 1
    if n< 0 or type(n) == float:
      return -1
    dp = [0, 1, 2, 3]
    for i in range(4, n + 1):
        dp.append(i)
        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])
    return dp[n]
In [105]:
evaluate_test_cases(get_square_sum_dp, tests1)
TEST CASE #0 Input: {'n': 11} Expected Output: 3 Actual Output: 3 Execution Time: 0.034 ms Test Result: PASSED TEST CASE #1 Input: {'n': 6} Expected Output: 3 Actual Output: 3 Execution Time: 0.017 ms Test Result: PASSED TEST CASE #2 Input: {'n': 27} Expected Output: 3 Actual Output: 3 Execution Time: 0.1 ms Test Result: PASSED TEST CASE #3 Input: {'n': 25} Expected Output: 1 Actual Output: 1 Execution Time: 0.096 ms Test Result: PASSED TEST CASE #4 Input: {'n': 0} Expected Output: 1 Actual Output: 1 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #5 Input: {'n': 1} Expected Output: 1 Actual Output: 1 Execution Time: 0.005 ms Test Result: PASSED TEST CASE #6 Input: {'n': 21.4} Expected Output: -1 Actual Output: -1 Execution Time: 0.002 ms Test Result: PASSED TEST CASE #7 Input: {'n': -71} Expected Output: -1 Actual Output: -1 Execution Time: 0.002 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[105]:
[(3, True, 0.034),
 (3, True, 0.017),
 (3, True, 0.1),
 (1, True, 0.096),
 (1, True, 0.003),
 (1, True, 0.005),
 (-1, True, 0.002),
 (-1, True, 0.002)]

As we can see, this took a lot less time than recursion and is much more efficient

In [81]:
jovian.commit()
[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aditya-pat10/minimum-square-sum

7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

  1. Create a list and populate it with the value of index
  2. Go through all smaller number to recursively find minimum
  3. Store result
  4. Return value at nth index

Let's save and upload our work before continuing.

In [ ]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "aakashns/python-problem-solving-template" on https://jovian.ai/ [jovian] Uploading notebook.. [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/aakashns/python-problem-solving-template

8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [106]:
from math import ceil, sqrt

def get_square_sum_dp(n):
    if n==0:
      return 1
    if n< 0 or type(n) == float:
      return -1
    dp = [0, 1, 2, 3]
    for i in range(4, n + 1):
        dp.append(i)
        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])
    return dp[n]
In [107]:
evaluate_test_cases(get_square_sum_dp, tests1)
TEST CASE #0 Input: {'n': 11} Expected Output: 3 Actual Output: 3 Execution Time: 0.033 ms Test Result: PASSED TEST CASE #1 Input: {'n': 6} Expected Output: 3 Actual Output: 3 Execution Time: 0.019 ms Test Result: PASSED TEST CASE #2 Input: {'n': 27} Expected Output: 3 Actual Output: 3 Execution Time: 0.1 ms Test Result: PASSED TEST CASE #3 Input: {'n': 25} Expected Output: 1 Actual Output: 1 Execution Time: 0.079 ms Test Result: PASSED TEST CASE #4 Input: {'n': 0} Expected Output: 1 Actual Output: 1 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #5 Input: {'n': 1} Expected Output: 1 Actual Output: 1 Execution Time: 0.004 ms Test Result: PASSED TEST CASE #6 Input: {'n': 21.4} Expected Output: -1 Actual Output: -1 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #7 Input: {'n': -71} Expected Output: -1 Actual Output: -1 Execution Time: 0.002 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[107]:
[(3, True, 0.033),
 (3, True, 0.019),
 (3, True, 0.1),
 (1, True, 0.079),
 (1, True, 0.003),
 (1, True, 0.004),
 (-1, True, 0.003),
 (-1, True, 0.002)]

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

In [ ]:
Complexity = O(n^2)

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..
In [ ]: