# spoj IITKWPCO

My code:

``````      #include <bits/stdc++.h>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
int a,ar;
int main()
{
int t,n,x,ans;
cin>>t;
while(t--)
{
memset(a,0,sizeof a);ans=0;
cin>>n;
rep(i,n)
{
cin>>x;
a[x]++;
ar[i]=x;
}
sort(ar,ar+n);//without this line solution is wrong.why??
rep(i,n) if(a[ar[i]*2]>0&&a[ar[i]]>0) {++ans;a[ar[i]*2]--;a[ar[i]]--;}
cout<<ans<<"\n";
}

return 0;

}

I think there is no need to sort the array ar[].But it is needed why??
``````
2 Likes

In this problem, we need to maximize the number of pairs of integers such that ar[i] and 2*ar[i] both are present in the array.

Suppose array ar[] contains {4,8,16,2}. If it is unsorted, then your code is making a pair of 4 and 8 ie {4,8} and there are no more pairs now that follow the given condition. Hence your output is 1 (which is non optimal and can be improved by sorting).

If the arrray is sorted, it becomes {2,4,8,16} and your code makes 2 pairs ie {2,4} and {8,16}. Your output is 2 (maximal) and you get AC.

2 Likes

Thanks a lot!!!

1 Like