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

  • answered 2018-04-14 19:11 Raghav

    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 and arr2. Then do a set_symmetric_difference on them. This will effectively run in linear time. Then create two sets out of them, say set1 and set2.

    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 in set2. Likewise do for arr2 as well and remove the element when necessary.

    This can be done in O(n2). 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 the arr2 by doing a binary search. Then the time complexity may shoot up to O(n2 log(n)).