there is some problem , i mean you taken some assumptions here. in first caes 1 and 4 have difference of 3 which is not less than 2 , am i missing something. also , if we have two replacement values , which will we replace , i mean excahnge if there are two chocies . I think your algo might work with little more brainstorming on it.
On Tue, Jan 4, 2011 at 8:09 PM, sunny <[email protected]> wrote: > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
