 # Perfect Squares

Given a positive integer ` n `, find the least number of perfect squares which sum to ` n `

## Example Test Cases

### Sample Test Case 1

Input grid: ` 5 `
Expected Output: ` 2 `
Explanation: We need minimum two perfect squares to sum up to 5. for example, 5 can be written as
` 5 = 1`2` + 2`2` `

### Sample Test Case 2

Input grid: ` 12 `
Expected Output: ` 3 `
Explanation: You need minimum of three perfect squares to write 12:
` 12 = 2`2` + 2`2` + 2`2` `

## Solution

We can solve this problem by using recursion and then memoizing the results.
Let ` f(n) ` be the minimum number of perfect squares needed to form ` n `.
Therefore, we can write ` f(n) = min(f(n - 1`2`), f(n - 2`2`), f(n - 3`2`), f(n - 4`2`),....f(n - i`2`)) + 1; for all i such that i`2` < n `
Since, we might end up computing this function again and again for same numbers, we can memoize the results and store it in an array/map as shown below in the implementation.

## Solution Implementation

```#include <bits/stdc++.h>
using namespace std;

int solve(vector& answer, int sum) {
int mi = INT_MAX;

// If the answer[sum] is not computed, compute it.
if (answer[sum] < 0) {
for(int i = 1; i*i <= sum; i++) {
mi = min(mi, solve(answer, sum - i*i) + 1);
}
answer[sum] = mi;
}

return answer[sum];
}

int main() {

int n = 13;

// answer[i] will store the minimum number of perfect squares needed to make i
vector answer(n + 1);

// if answer[i] is -1, it means that we have not computed answer[i] before.

fill(answer.begin(), answer.end(), -1);

// Since, the number of ways of forming 0 with perfect squares is 0
answer = 0;

cout << "The minimum perfect squares needed are " << solve(answer, n) << "\n";
}
```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.