Most efficient algorithm to neutralize all positive and negative So I've been lately working on an app which requires me to code this algorithm. But I'm unsure what I've come up with is the most efficient algorithm.
Say I have 2 sets (or rather arrays, as there can be duplicates) A and B with all positive values in A and all negative values in B.
Ex - 
A = {1, 3, 1} (sum = 5)
B = {-2, -3} (sum = -5)
The sum of all elements in both the array will always be 0 (-5 + 5 = 0). The number of elements might be different.
Now what is the most efficient way (minimum steps) to neutralize all values? For example one way:
-3 + 1 = -2
Now A looks like: {0, 3, 1} and B looks like: {-2, -2}
Then -2 + 3 = 1
Now A looks like: {0, 1, 1} and B looks like {0, -2}
Now doing 2 more steps. Hence total of 4 steps. Can I compute the most efficient solution for this? How?
My take was to neutralize first the exact matching values (makes 2 elements 0 directly). Then look for biggest in positive and start merging with biggest in negative as long as possible. But it is just intuitive thinking from my side. Is there any efficient algorithm to this? 
 A: The next algorithm can be used.
$(1)$Let us find the opposite pairs.
At first, to sort arrays $A$ and $B$. The directs of moving will be of modules decreasing.
If the sum of elements in the current pair is positive, use the next $A,$ else the next $B.$
$A = (3,1,1), B = (-3,-2) \rightarrow A=(1,1),\ B = (-2).$
Note.
The classical knapsack problem remains, requiring a search of variants. Nevertheless, one of the best strategies is "greedy" bust.
So...
$(2)$ Repeat both of cycles in arrays. If the sum of the current elements are positive, it must be saved in new array A', otherwise in new B'. Used elements must be deleted.
Results:
$A=(1,1),\ B = (-2) \rightarrow A=(1),\ B=(),\ B' = (-1).$
$(3)$ Merge $A = A \cup A',\quad B = B \cup B',$ then go to $(1).$
In details
Let $A=(3,2,1),\ B=(-4,-2),$\ then:
$$(1):\quad A_0+B_0 < 0\rightarrow A_0+B_1>0\rightarrow A_1+B_1 = 0\dots\rightarrow A=(3,1),\ B=(-4).$$
$$(2): A_0+B_0=-1\rightarrow A=(1),\ B=(), B'=(-1).$$
$$(3): A=(1),\ B=(-1).$$
$$(1): A_0+B_0=0\rightarrow \text{done!}$$
A: Partial answer.
If I understood correctly, the only valid operation is picking one element from A and one element from B, computing their sum, then inserting the result and 0 where appropriate. Repeat until both sets are all 0s.
Then, in every step, you replace either 1 or 2 numbers with 0 (zero). So, at best you can do about size-of-one-set operations, and at most size(A)+size(B) operations. Linear.
How much better are you looking for, and why? How costly are the operations?
Update: How you assign costs to operations, and what it is you want to minimize is important. For example, walking through both sets [for example, say, put each on a stack, etc.] and "neutralizing" pairs as you see them would cost O(size(A)+size(B)), but just sorting both sets costs a factor of log() more.
