Easy Implementation using map and reverse iterator in O(n)


#1

int Solution::solve(vector &A) {
map<int,int>m;
int n=A.size();
for(int i=0;i<n;i++)
{
m[A[i]]++;
}
map<int,int>::reverse_iterator it;
long long sum=0;
for(it=m.rbegin();it!=m.rend();it++)
{
if(it->first==sum)
return 1;
sum+=it->second;
}
return -1;
}