Fair Candy Swap

easy hash set array math

Problem

Alice and Bob each have boxes of candy. aliceSizes[i] is the number of candies in Alice's i-th box and bobSizes[j] is the number in Bob's j-th box. They want to exchange exactly one box each so that afterwards they have the same total number of candies. Return [x, y] where x is the size of the box Alice gives and y is the size Bob gives. An answer is guaranteed to exist.

InputaliceSizes = [1, 1], bobSizes = [2, 2]

Output[1, 2]

Alice (total 2) gives a 1, Bob (total 4) gives a 2. New totals: Alice 2 − 1 + 2 = 3, Bob 4 − 2 + 1 = 3.

aliceSizes (comma-separated)

bobSizes (comma-separated)

def fair_candy_swap(aliceSizes, bobSizes):
    diff = (sum(aliceSizes) - sum(bobSizes)) // 2
    bob = set(bobSizes)
    for a in aliceSizes:
        b = a - diff
        if b in bob:
            return [a, b]
    return None

function fairCandySwap(aliceSizes, bobSizes) {
  const sum = arr => arr.reduce((s, x) => s + x, 0);
  const diff = (sum(aliceSizes) - sum(bobSizes)) / 2;
  const bob = new Set(bobSizes);
  for (const a of aliceSizes) {
    const b = a - diff;
    if (bob.has(b)) return [a, b];
  }
  return null;
}

class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sa = 0, sb = 0;
        for (int x : aliceSizes) sa += x;
        for (int x : bobSizes) sb += x;
        int diff = (sa - sb) / 2;
        Set<Integer> bob = new HashSet<>();
        for (int x : bobSizes) bob.add(x);
        for (int a : aliceSizes) {
            int b = a - diff;
            if (bob.contains(b)) return new int[]{ a, b };
        }
        return null;
    }
}

vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
    int sa = 0, sb = 0;
    for (int x : aliceSizes) sa += x;
    for (int x : bobSizes) sb += x;
    int diff = (sa - sb) / 2;
    unordered_set<int> bob(bobSizes.begin(), bobSizes.end());
    for (int a : aliceSizes) {
        int b = a - diff;
        if (bob.count(b)) return { a, b };
    }
    return {};
}

Explanation

Alice gives one box of size a and gets one of size b from Bob. The clever part is realizing that the size b we need is forced by the totals, so we never have to try every pair.

For the totals to end equal, the candies Alice loses minus what she gains must close half the gap between them. Define diff = (sum(alice) - sum(bob)) / 2. Then for any box a Alice gives, the box she needs back is exactly b = a - diff.

So we put all of Bob's box sizes into a hash set for instant lookups. We loop over Alice's boxes, compute b = a - diff for each, and the moment b is in Bob's set we return [a, b].

Example: aliceSizes = [1, 1], bobSizes = [2, 2]. Sums are 2 and 4, so diff = (2 - 4) / 2 = -1. For Alice's box 1, we need b = 1 - (-1) = 2, which is in Bob's set, so the answer is [1, 2].

The set makes each check instant, so one pass over Alice's boxes finds the swap.

Time: O(m + n) Space: O(n)