Fair Candy Swap - LeetCode Problem Problem Description Alice and Bob have different total amounts of candy. You are given two integer arrays aliceSizes and bobSizes, where aliceSizes[i] is the number of candies in the ith box of candy that Alice has, and bobSizes[j] is the number of candies in the jth box of candy that Bob has.

Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy.

Constraints: 1 <= aliceSizes.length, bobSizes.length <= 10^4 1 <= aliceSizes[i], bobSizes[j] <= 10^5 Alice and Bob have different total numbers of candies. There will be at least one valid answer. Example 1: cpp Copy code Input: aliceSizes = [1,1], bobSizes = [2,2] Output: [1, 2] Example 2: cpp Copy code Input: aliceSizes = [1,2], bobSizes = [2,3] Output: [1, 2] Example 3: cpp Copy code Input: aliceSizes = [2], bobSizes = [1,3] Output: [2, 3] Solution Approach The key idea is to balance the total number of candies Alice and Bob have by exchanging one candy box. Here’s the approach:

Calculate Total Candies: First, calculate the total number of candies for both Alice and Bob. Find the Difference: Calculate the difference in their totals divided by 2. This gives the amount Alice must give to Bob (or vice versa). Efficient Search with Set: Use a set to quickly check if Bob has the required candy size that balances the totals after the swap. The time complexity is O(n + m), where n is the length of aliceSizes and m is the length of bobSizes.

C++ Solution: The solution is implemented in C++ and can be found in the fair_candy_swap.cpp file.

cpp class Solution { public: vector fairCandySwap(vector& aliceSizes, vector& bobSizes) { int s1 = accumulate(aliceSizes.begin(), aliceSizes.end(), 0); int s2 = accumulate(bobSizes.begin(), bobSizes.end(), 0); int diff = (s1 - s2) >> 1; unordered_set s(bobSizes.begin(), bobSizes.end()); vector ans; for (int& a : aliceSizes) { int target = a - diff; if (s.count(target)) { ans = vector{a, target}; break; } } return ans; } };

Time Complexity: O(n + m), where n is the size of aliceSizes and m is the size of bobSizes. Space Complexity: O(m), due to the additional space used by the set for Bob's candy sizes.