Best Logic to implement comparison of two arrays
I have two arrays arr 1 and arr 2, here both the arrays will have some common items and many uncommon items, first the common items should be removed from both the arrays.
therefore for each uncommon item in arr 1 may probably be a sum of two or more values in arr 2 or vice versa.if the sum is found the values must be removed from the respective arrays. Finally the output should only be the unmatched values on both the arrays
I need a logic where i can do this calculation in much faster way.
1 answer

I'm not going to give out the code that implements your logic but rather I would be happy to point you in the right direction.
I code in C++, so I'm gonna answer with respect to that. If you want a different language, I'm sure you can freely do so.
To remove the common elements:
You first sort the arrays
arr1
andarr2
. Then do a set_symmetric_difference on them. This will effectively run in linear time. Then create two sets out of them, sayset1
andset2
.To remove pairs that sum up to an element in the other array
For this, you need to loop through all the possible pairs of elements in
arr1
and check if this sum of this pair exists inset2
. Likewise do forarr2
as well and remove the element when necessary.This can be done in O(n^{2}). If you don't want to create the extra sets, you can always trade performance for memory, by just looping through the pairs of
arr1
and checking for the sum in thearr2
by doing a binary search. Then the time complexity may shoot up to O(n^{2} log(n)).