In this post, we are going to solve Perfect Squares DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

## Perfect Squares DSA Problem Statement

Given an integer

$n$, return the least number of perfect square numbers that sum to

$n$.

Input

The input consists of a single integer

$n$

$-$

$(1\le n\le {10}^{9})$.

Output

The output should consist of a single integer

$-$ the minimum number of perfect square numbers that sum to

$n$.

Example

Input

5

Output

2

## Problem Solution in C++

```
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin>>n;
vector<long long>ans;;
for(long long i=1;(long long)i*i<=n;i++){
ans.push_back(i*i);
}
if(ans.back()==n){
cout<<1;
return 0;
}
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans.size();j++){
if(ans[i]+ans[j]==n){ cout<<2;
return 0;
}
}
}
while(n%4==0){
n=n/4;
}
if(n%8==7){
cout<<4;
return 0;
}
cout<<3;
return 0;
}
```

## Leave a Reply