Fair Candy Swap

Problem Statement

In this problem, Alice and Bob have collections of candy boxes, each containing a certain number of candies. The collections are represented as integer arrays aliceSizes and bobSizes, where each element corresponds to the number of candies in a specific candy box. The goal is to find a single box from Alice's collection and another from Bob's collection to swap, so that after the exchange, both Alice and Bob have the same total amount of candies. Each person’s total amount of candy is the sum of their individual boxes. The function should return an array consisting of two integers, representing the number of candies in the boxes to be exchanged between Alice and Bob. If multiple solutions are possible, any valid solution can be returned.

Examples

Example 1

Input:

aliceSizes = [1,1], bobSizes = [2,2]

Output:

[1,2]

Example 2

Input:

aliceSizes = [1,2], bobSizes = [2,3]

Output:

[1,2]

Example 3

Input:

aliceSizes = [2], bobSizes = [1,3]

Output:

[2,3]

Constraints

• 1 <= aliceSizes.length, bobSizes.length <= 104
• 1 <= aliceSizes[i], bobSizes[j] <= 105
• Alice and Bob have a different total number of candies.
• There will be at least one valid answer for the given input.

Approach and Intuition

To solve this problem, you need to ensure that after Alice and Bob swap one box each, their total number of candies becomes equal. For this, one can leverage a handy mathematical trick involving sum differences:

1. Firstly, calculate the total number of candies each person currently possesses.
2. Determine the difference needed to balance the candies between them if they were to exchange boxes.
3. Transform the problem into a two-sum like task where you seek to find two values, one from each array (aliceSizes and bobSizes), that when swapped would balance their totals.

Let's simplify the process into steps:

1. Compute the sum of aliceSizes and bobSizes, called sumA and sumB respectively.
2. Calculate the difference diff = (sumA - sumB) / 2.
   • The division by 2 is crucial because for the totals to match after an exchange, Alice must lose diff candies, and Bob must gain diff candies or vice versa.
3. Create a set from one of the arrays for constant time look-up.
   • For example, put all elements of aliceSizes in a set.
4. Traverse through the other array (e.g., bobSizes), and for each candy count b in bobSizes, check if b + diff exists in the set of aliceSizes.
   • If it does, this implies that b coming from Bob's box, when increased by diff, equals a candy count in one of Alice's boxes. This can be your potential exchange pair.
5. Return the box pair that balances their candy counts.

By employing this approach based on set look-ups and simple arithmetic operations, we can efficiently determine a valid box swap that allows Alice and Bob to equalize their total candy count.

Solutions

class Solution {
    public int[] findSwapValues(int[] Alice, int[] Bob) {
        int sumAlice = 0, sumBob = 0;
        for (int candy : Alice) sumAlice += candy;
        for (int candy : Bob) sumBob += candy;
        int diff = (sumBob - sumAlice) / 2;
    
        Set<Integer> bobCandies = new HashSet();
        for (int candy : Bob) bobCandies.add(candy);
    
        for (int candy : Alice)
            if (bobCandies.contains(candy + diff))
                return new int[]{candy, candy + diff};
    
        throw null;
    }
}