Fair Candy Swap

There are two friends with unequal candy, how do they swap such that they both have equal candy

Fair Candy Swap

Problem

Alice and Bob have a different total number of candies. You are given two integer arrays:

• aliceSizes[i] is the number of candies in the ith box that Alice has.
• bobSizes[j] is the number of candies in the jth box that Bob has.

They want to exchange one box each, so that after the exchange both have the same total number of candies.

Return an array answer:

• answer[0] is the number of candies in the box Alice gives.
• answer[1] is the number of candies in the box Bob gives.

If there are many answers, return any one. At least one answer always exists.

Examples

Example 1

Input: aliceSizes = [1,1], bobSizes = [2,2]
Output: [1,2]

• Alice has 2 candies and Bob has 4.
• Alice gives a box of 1 and gets a box of 2. Alice now has 3.
• Bob gives a box of 2 and gets a box of 1. Bob now has 3.

Example 2

Input: aliceSizes = [1,2], bobSizes = [2,3]
Output: [1,2]

• Alice has 3 and Bob has 5.
• After the swap, both have 4.

Example 3

Input: aliceSizes = [2], bobSizes = [1,3]
Output: [2,3]

• Alice has 2 and Bob has 4.
• After the swap, both have 3.

Constraints

• 1 <= aliceSizes.length, bobSizes.length <= 10^4
• 1 <= aliceSizes[i], bobSizes[j] <= 10^5
• Alice and Bob start with different totals.
• At least one valid answer exists.

Main Idea

Let us use some names:

• sumA is Alice's total and sumB is Bob's total.
• a is the box Alice gives, and b is the box Bob gives.

After the swap:

• Alice's total is sumA - a + b.
• Bob's total is sumB - b + a.

We want both totals to be equal:

sumA - a + b = sumB - b + a

Now we solve for b:

2b - 2a = sumB - sumA
b = a + (sumB - sumA) / 2

Let diff = (sumB - sumA) / 2. Then:

b = a + diff

So for each box a that Alice has, the box Bob must give is exactly a + diff. We only need to check whether Bob has such a box.

To check this fast, we put all of Bob's boxes in a Set. A Set checks "is this value here?" in O(1) time.

Why is diff always a whole number? A valid answer is guaranteed to exist. This means sumB - sumA must be even, so dividing by 2 is safe.

Brute Force (For Comparison)

We try every pair (a, b) and check if the totals become equal.

var fairCandySwap = function (alice, bob) {
    let sumA = alice.reduce((x, y) => x + y, 0);
    let sumB = bob.reduce((x, y) => x + y, 0);

    for (let a of alice) {
        for (let b of bob) {
            if (sumA - a + b === sumB - b + a) {
                return [a, b];
            }
        }
    }
};

Complexity

• Time Complexity: O(n * m)
  • n is the size of Alice's array and m is the size of Bob's array.
  • We check every pair.
• Space Complexity: O(1)
  • We use only a few variables.

Solution: Sum + Set

var fairCandySwap = function (alice, bob) {
    // total candies of each person
    let sumA = alice.reduce((a, b) => a + b, 0);
    let sumB = bob.reduce((a, b) => a + b, 0);

    // how much bigger Bob's box must be than Alice's box
    let diff = (sumB - sumA) / 2;

    // put Bob's boxes in a set for fast lookup
    let setB = new Set(bob);

    for (let a of alice) {
        // Bob must have a box of size a + diff
        if (setB.has(a + diff)) {
            return [a, a + diff];
        }
    }
};

How the Code Works

Step 1: Find both totals

• reduce adds all the numbers in each array.
• sumA is Alice's total and sumB is Bob's total.

Step 2: Find diff

• diff = (sumB - sumA) / 2 is the gap between the two boxes we swap.
• If diff is positive, Bob's box is bigger. If diff is negative, Bob's box is smaller.

Step 3: Make a Set of Bob's boxes

• setB holds all of Bob's box sizes.
• Duplicates do not matter, because we only need to know if a size exists.

Step 4: Check each of Alice's boxes

• For each box a, the partner box is a + diff.
• If setB.has(a + diff) is true, we return [a, a + diff].
• The problem guarantees an answer, so the loop always returns a result.

Dry Run

Let us take aliceSizes = [1, 2] and bobSizes = [2, 3].

• sumA = 3, sumB = 5.
• diff = (5 - 3) / 2 = 1.
• setB = {2, 3}.

Check the answer:

• Alice gives 1 and gets 2. Her total is 3 - 1 + 2 = 4.
• Bob gives 2 and gets 1. His total is 5 - 2 + 1 = 4.
• Both have 4.

Now let us take aliceSizes = [2] and bobSizes = [1, 3].

• sumA = 2, sumB = 4.
• diff = (4 - 2) / 2 = 1.
• setB = {1, 3}.

Complexity

• Time Complexity: O(n + m)
  • n is the size of Alice's array and m is the size of Bob's array.
  • Finding both sums takes O(n + m).
  • Building the Set takes O(m).
  • The loop over Alice's boxes takes O(n), and each has check is O(1) on average.
• Space Complexity: O(m)
  • The Set stores up to m values from Bob's array.

Comparison

Summary

• After swapping box a (Alice) and box b (Bob), both totals must be equal.
• This gives a simple rule: b = a + (sumB - sumA) / 2.
• We store Bob's boxes in a Set, so we can check if the needed box exists in O(1) time.
• For each of Alice's boxes, we check if the partner box is in the Set.
• The solution runs in O(n + m) time and uses O(m) space. It trades a little memory for much better speed than brute force.