Solution


Approach 1: Solve the Equation

Intuition

If Alice swaps candy x, she expects some specific quantity of candy y back.

Algorithm

Say Alice and Bob have total candy respectively.

If Alice gives candy , and receives candy , then Bob receives candy and gives candy . Then, we must have

for a fair candy swap. This implies

Our strategy is simple. For every candy that Alice has, if Bob has candy , we return . We use a Set structure to check whether Bob has the desired candy in constant time.

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: , the space used by setB. (We can improve this to by using an if statement.)


Analysis written by: @awice.