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.