Home » Interview coding problems/challenges

# Get Minimum Squares

**Get Minimum Squares**: Here, we are going to learn how to compute minimum number of squares need to sum a number N?

Submitted by Radib Kar, on February 10, 2020

**Description:**

In this article we are going to see **how to compute minimum number of squares need to sum a number N?** This article has been featured in interview rounds of Amazon, Wipro.

**Problem statement:**

Given a number **N**, write a program to print the minimum number of squares that sums to **N**.

Input: N = 41 Output: Minimum number of squares needed: 2

**Explanation with example**

We can think similar way as the coin change problem (refer to my article on coin change). We can start with the greedy approach and can see whether it works or not.

So, a greedy approach can be

First thing is to find whether we will be able to find answers for any number **N**. Is it possible to find squares that will sum up to **N**. Yes, we will be able to find for any number **N** because 1 is itself a square and we can get any number by summing 1?

Since we are to find the minimum number of squares it's apparent that we should pick the square with the maximum value closest to **N** and keep trying with that until the remaining sum is less the square. Then on course, we keep choosing the next best one. So, the algorithm would be like.

1) Let, count=0 to count minimum number of squares to sum 2) Pick up square x closest to N 3) While N≥x N=N-x count=count+1 4) if N=0 Go to Step 7 5) Pick up the next best square value <x & closest to N .assign it to x 6) Go to Step 2 7) End. count is the minimum number of squares needed to sum up.

Let's see whether the above greedy algorithm leads to the desired result or not.

N = 41 The square value closest to 41 is 36 count = 1, N = 5 Next best square value is 4 count = 2, N = 1 Next best square value is 1 count = 3, N = 0 So, minimum number of squares needed is 3 But is it really minimum? If we choose 25 and 16, that sums up to 41 and we need only two squares. That's the minimum, not 3. So, greedy does not work as the local optimum choices doesn't make global optimum choice. Hence, we need dynamic programing.

**Problem Solution Approach**

In the coin change problem (refer to my article of coin change) we had an amount M and n number of coins, { C_{1}, C_{2}, ..., C_{n}} to make change. We can think this minimum square problem as we did in coin change problem. We can frame this problem lie the coin change problem, where, *Amount M = Number N*

*Coin denominations { C _{1}, C_{2}, ..., C_{n}} = {x_{1}, x_{2}, ..., x_{n} } where x_{i} is square and x_{i}<N*

Now,

We have two choice for any x_{i},

- Use x
_{i}and recur for N-x_{i} - Don't use x
_{i}and recur for N with other squares

*f(n)= minimum number of squares needed to sum n*

We can formulate the above recursion using DP.

1) Initialize DP[N+1] with index value [for any number 0 to N, minimum number of squares needed is initially same as index no, i.e., minimum number squares needed for number i=i( i times 1) ] 2) DP[0]=0 //base case of above recursion 3) Create X[n]with squares<N 4) for i=1 to N //iterate numbers for squares x_{i}= X[0] to X[n] If i>=x_{i}&& DP[i-x_{i}]+1<DP[i]) DP[i]=DP[i-x_{i}]+1; //update value End for End forThe result is DP[N]

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; int min_square(int m) { int DP[m + 1]; //base value for (int i = 1; i <= m; i++) DP[i] = i; DP[0] = 0; //create the array of squares to be used to sum vector<int> a; for (int i = 1;; i++) { if (i * i <= m) a.push_back(i * i); else break; } int n = a.size(); for (int i = 1; i <= m; i++) { //iterate for the numbers for (int j = 0; j < n; j++) { //iterate on the squares if (i >= a[j] && DP[i - a[j]] + 1 < DP[i]) DP[i] = DP[i - a[j]] + 1; } } //result return DP[m]; } int main() { int n, item, m; cout << "Enter the number\n"; cin >> n; int ans = min_square(n); cout << "Minimum number of squares needed: " << ans << endl; return 0; }

**Output**

Enter the number 41 Minimum number of squares needed: 2

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions