How about this algorithm: 1 sort the given array in ascending order 2 traverse from back that is greater to smaller 3 put the 1st read in arrayA and the 2nd read in arrayB 4 put the 3rd read in arrayB and the 4th read in arrayA (notice we have reverse the order of putting the values) 5 repeat the process from step 3 until you have read all the values 6 find sum of the two arrays arrayA and arrayB (notice at this point all values are read and both sets have same no. of elements) 7 find diff of their sums 8 find half value of the diff calculated say that value is 'x' 9 now try to find one no. in both the array with their diff <= x such that greater no. is from arrayA and smaller is from arrayB if sum of A > sum of B else viceversa. 10 if you don't find any such two no. then the current values in arrayA and arrayB is the solution we are looking for 11 else just replace two no. find in step 9 and repeat the process from step 6
Let me try to explain the algo with these two examples: Example 1: given: 1 7 6 4 9 12 sorted : 1 4 6 7 9 12 arrayA: 12 arrayB: arrayA: 12 arrayB: 9 arrayA: 12 arrayB: 9 7 arrayA: 12 6 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 1 at this point all values are read and both sets have same no. of elements now sum of arrayA = 22 now sum of arrayB = 18 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff <= 2 with greater no. in arrayA and smaller in arrayB (reason being here sum of A > sum of B) the two no. are 4 in arrayA and 1 in arrayB replace these two, so now we have: arrayA: 12 6 1 arrayB: 9 7 4 now sum of arrayA = 19 now sum of arrayB = 20 diff of sum = 1 half of diff = 1/2 = 0 (we consider integer values only) Thus the given subsets is the solution: arrayA: 12 6 1 arrayB: 9 7 4 ---------------------------------------------------------------------------------------------------------------------------------------------------- Example 2: given: 5 18 3 9 11 34 sorted : 3 5 9 11 18 34 arrayA: 34 arrayB: arrayA: 34 arrayB: 18 arrayA: 34 arrayB: 18 11 arrayA: 34 9 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 3 at this point all values are read and both sets have same no. of elements now sum of arrayA = 48 now sum of arrayB = 32 diff of sum = 16 half of diff = 16/2 = 8 (we consider integer values only) now try to find one no. in both the array with their diff <= 8 with greater no. in arrayA and smaller in arrayB (reason being here sum of A > sum of B) the two no. are 9 in arrayA and 3 in arrayB replace these two, so now we have: arrayA: 34 3 5 arrayB: 18 11 9 now sum of arrayA = 42 now sum of arrayB = 38 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff <= 4 with greater no. in arrayA and smaller in arrayB (reason being here sum of A > sum of B) We can not found any such two no. in these two arrays, thus the given subsets is the solution: arrayA: 34 3 5 arrayB: 18 11 9 ----------------------------------------------------------------------------------------------------------------------------------------------------- I have tried this algo on various size of arrays with all sort of values and it seems to be working as expected. -Sachin -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
