spoj IITKWPCO

question link: here

My code:

      #include <bits/stdc++.h>
      #include <iostream>
      #define rep(i,n) for(int i=0;i<n;++i)
      using namespace std;
     int a[2000010],ar[105];
     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??
 Please help anyone ???
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