Fair Candy Swap

Fair Candy Swap

What is this problem about?

The Fair Candy Swap interview question features two friends, Alice and Bob, each with an array of candy bar sizes. They want to exchange exactly one candy bar each so that after the exchange, they both have the same total weight of candy. You need to return an array [aliceSize, bobSize] representing the sizes of the candy bars they should swap. The problem guarantees that at least one such pair exists.

Why is this asked in interviews?

This is a popular "Easy" Hash Table and Math interview pattern used by companies like Amazon and Google. It tests your ability to derive a simple algebraic equation from a word problem and then optimize the search for a solution. It evaluates whether you can use a Hash Set to turn an O(N*M) brute-force search into an O(N+M) efficient lookup.

Algorithmic pattern used

1. Math: Let $S_A$ and $S_B$ be the total sums of Alice's and Bob's candy sizes.
   • If Alice swaps $x$ and Bob swaps $y$:
   • $S_A - x + y = S_B - y + x$
   • $2y - 2x = S_B - S_A$
   • $y = x + (S_B - S_A) / 2$
2. Hash Table:
   • Calculate total sums $S_A$ and $S_B$.
   • Calculate the required difference delta = (S_B - S_A) / 2.
   • Store all of Bob's candy sizes in a Hash Set.
   • Iterate through Alice's candies. For each $x$, check if x + delta exists in Bob's set.

Example explanation

Alice: [1, 2], Bob: [2, 3]

1. $S_A = 3, S_B = 5$.
2. delta = (5 - 3) / 2 = 1.
3. Bob's set: {2, 3}.
4. Alice's $x = 1$: $1 + 1 = 2$. Is 2 in Bob's set? Yes! Result: [1, 2]. (Check: Alice: $3-1+2=4$. Bob: $5-2+1=4$. Correct!)

Common mistakes candidates make

• Nested Loops: Using two loops to check every pair, resulting in O(N*M) complexity.
• Incorrect Formula: Miscalculating the delta (e.g., forgetting the division by 2).
• Not using a Set: Searching Bob's array linearly for every $x$ instead of using a set for O(1) lookup.

Interview preparation tip

Whenever you have an equation with two unknowns ($x$ and $y$) and two lists of possible values, the most common optimization is to fix $x$ and use a Hash Set to find if the required $y$ exists in the other list.