divide the array
How will you divide an array of approx 100 elements(integer) into two sub sets
of 50 each such that the difference between both the subsets is the
minimum possible .
of 50 each such that the difference between both the subsets is the
minimum possible .
//let the given array be a[100]
ReplyDeletesort(A); //in decreasing order
//B[50] and C[50] are required subsets
B[0]=A[0];
C[0]=A[1];
int d=A[0]-A[1],i,j=1;
for(i=2;i<99;i+=2,j++)
{
if(d>0){
B[j]=A[i+1];
C[j]=A[i];
}
else
{
B[j]=A[i];
C[j]=A[i+1];
}
d+=B[j]-C[j];
}
i suppose this should work fine...time complexity O(nlogn).