{x}
blog image

Fair Candy Swap

Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice has and bobSizes[j] is the number of candies of 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. The total amount of candy a person has is the sum of the number of candies in each box they have.

Return an integer array answer where answer[0] is the number of candies in the box that Alice must exchange, and answer[1] is the number of candies in the box that Bob must exchange. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.

 

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.

Solution Explanation for Fair Candy Swap

The problem asks to find a pair of candies, one from Alice's collection and one from Bob's, such that after exchanging them, both Alice and Bob have the same total number of candies.

Approach:

The core idea is to leverage the fact that the difference in the total number of candies between Alice and Bob must be evenly distributed after the swap. Let's denote:

  • sum_alice: The sum of candies Alice has.
  • sum_bob: The sum of candies Bob has.
  • x: The number of candies Alice gives to Bob.
  • y: The number of candies Bob gives to Alice.

After the swap, we want:

sum_alice - x + y = sum_bob - y + x

Simplifying this equation, we get:

2y = 2x + sum_bob - sum_alice

y = x + (sum_bob - sum_alice) / 2

This shows that y can be directly calculated if we know x and the difference between the sums is even. Since the problem guarantees a solution exists, the difference in sums will always be an even number.

The algorithm proceeds as follows:

  1. Calculate the total candies: Calculate sum_alice and sum_bob.
  2. Find the difference: Calculate diff = (sum_alice - sum_bob) / 2. This represents the difference that needs to be compensated by the candy swap. A bitwise right shift (>> 1) is used as an efficient way to divide by 2.
  3. Use a HashSet (or Set in other languages): Create a set (HashSet in Java, set in Python) containing Bob's candies for efficient lookup.
  4. Iterate and check: Iterate through Alice's candies. For each candy x, calculate y = x - diff. Check if y exists in Bob's set. If it does, we've found the pair (x, y).
  5. Return the pair: Return [x, y].

Time Complexity Analysis:

  • Calculating the sums takes O(m + n) time, where m and n are the lengths of aliceSizes and bobSizes respectively.
  • Creating the set takes O(n) time.
  • Iterating through Alice's candies and checking for y in the set takes O(m) time in average case (assuming a hash set or hash table with average constant-time lookup). In the worst-case scenario (e.g., a poorly implemented hash set), this could become O(m*n).

Therefore, the overall time complexity is O(m + n) on average and O(m*n) in the worst case.

Space Complexity Analysis:

The space complexity is dominated by the set used to store Bob's candies, which is O(n) in size.

Code Examples:

The code examples provided demonstrate the algorithm in Python, Java, C++, and TypeScript. They all follow the same basic approach outlined above. The differences are primarily due to the syntax and standard library functions of each language. Note that the Python solution uses a set for efficiency, while the TypeScript solution uses includes(), which might have slightly worse performance on large arrays. The C++ solution uses accumulate for efficient sum calculation.

Improvements

The worst-case time complexity of O(m*n) can be avoided by sorting Bob's candies first and using binary search during the iteration on Alice's candies. The binary search part will drop the time complexity to O(m log n).