Approach 1: Solve the Equation
If Alice swaps candy
x, she expects some specific quantity of candy
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.
Time Complexity: .
Space Complexity: , the space used by
setB. (We can improve this to by using an if statement.)
Analysis written by: @awice.