# Perfect Squares DSA Problem Solution

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$$n$, return the least number of perfect square numbers that sum to

$n$$n$.

Input

The input consists of a single integer

$n$$n$

$-$$-$

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

Output

The output should consist of a single integer

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

$n$$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;
}