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
, return the least number of perfect square numbers that sum to
.
Input
The input consists of a single integer
.
Output
The output should consist of a single integer
the minimum number of perfect square numbers that sum to
.
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;
}