There are different ways to approach this question. I am presenting the greedy approach. answered 26 Sep '14, 20:40
@thunderking, Thanks for the approach. I am having doubt for this case: x,x,ax,bx,bx. So A[0] = x; A[1] = x; A[2] = ax; A[3] = bx; A[4] = bx; Now suppose you sent element x,x,bx,bx to Set B. Then answer for the following case will be "NO". Please correct me if I am wrong.
(27 Sep '14, 02:36)
It is given in the problem statement that the all numbers are distinct, therefore this case never arises.
(27 Sep '14, 05:24)
Thank you :)
(28 Sep '14, 09:47)
suppose the array is {6,7} a=13 b=12. Then this approach will not give the correct answer. I think we need to handle the case when x=a/2 or x=b/2.
(28 Sep '14, 15:11)
@sikander_nsit if the array is {6,7} and a=13,b=12, then this approach will give the correct answer because as I have written in the explanation, we assume b is greater and if it is not, we swap A and B to make it so then both 6 and 7 will go to set B which is 13. This will also handle the case if x=a/2 or b/2 as we are trying to find ax or bx except x itself.
(29 Sep '14, 01:15)
Thanks...got it.
(02 Oct '14, 02:56)
showing 5 of 6
show all

Another obvious approach could be by formulating the problem as a perfect bipartite matching problem and then use HopcroftKarp algorithm for solving it. How to identify it as a bipartite matching problem? It's quite easy to make a note that the array needs to be split into 2 disjoint sets. This pretty much indicates that one can use bipartite matching algortihm. Why perfect? This part was easy enough to figure out as it was clearly mentioned in the problem:
Hope that helps :) answered 29 Sep '14, 00:54
