Domain 1EasyCORE

Fair Candy Swap

Alice and Bob have candy bars of different sizes. Alice has an array `A` where `A[i]` represents the size of the i-th bar she has, and Bob has an array `B` where `B[j]` represents the size of the j-th bar he has. They want to exchange one candy bar each so that after the swap, both have the same total amount of candy.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

888. Fair Candy Swap

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 59.1%


Problem Breakdown

Alice and Bob have candy bars of different sizes. Alice has an array A where A[i] represents the size of the i-th bar she has, and Bob has an array B where B[j] represents the size of the j-th bar he has. They want to exchange one candy bar each so that after the swap, both have the same total amount of candy.

Inputs:

  • Two arrays of integers, A and B, representing the sizes of the candy bars Alice and Bob have, respectively.

Outputs:

  • An integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

Implicit Constraints/Tricky Edge Cases:

  • The total amount of candy each person has before the swap is different.
  • There is guaranteed to be at least one valid solution.
  • Arrays can have up to 10,000 elements, so efficiency is important.

Intuition

The brute-force approach would involve checking every possible pair of candy bars from Alice and Bob to see if swapping them results in equal total amounts. This approach has a time complexity of O(n * m), where n is the length of array A and m is the length of array B. Given the constraints, this is inefficient.

The key insight is that if we let sumA be the sum of all candy bars Alice has and sumB be the sum of all candy bars Bob has, then for any swap where Alice gives a bar of size x to Bob and receives a bar of size y, the following must hold: [ \text{sumA} - x + y = \text{sumB} - y + x ] Simplifying this equation gives us: [ 2(y - x) = (\text{sumB} - \text{sumA}) ] Thus, ( y - x = \frac{\text{sumB} - \text{sumA}}{2} ). This means we can find the difference in sums and use it to determine which candy bars to swap.

Approach

  1. Calculate sumA as the sum of all elements in array A.
  2. Calculate sumB as the sum of all elements in array B.
  3. Compute the difference diff = (sumB - sumA) // 2. This is the amount by which each candy bar Alice gives must be smaller than the one she receives.
  4. Convert array B into a set for O(1) average-time complexity lookups.
  5. Iterate through each candy bar in array A. For each candy bar x, check if there exists a candy bar y in Bob’s collection such that ( y = x + \text{diff} ).
  6. Return the pair [x, y].

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of array A and m is the length of array B. We need to sum up the elements in both arrays and then iterate through one of them.
  • Space Complexity: O(m) for storing Bob’s candy bars in a set.

Solution

def fairCandySwap(A, B):
    sumA = sum(A)
    sumB = sum(B)
    diff = (sumB - sumA) // 2
    
    # Convert B to a set for O(1) lookups
    setB = set(B)
    
    for x in A:
        y = x + diff
        if y in setB:
            return [x, y]

Edge Cases Handled

  • Different Lengths: The solution works regardless of the lengths of arrays A and B.
  • Same Candy Bar Sizes: If Alice and Bob have candy bars of the same size, they will be swapped.
  • Large Input Sizes: The use of a set for Bob’s candy bars ensures that the solution remains efficient even with large inputs.