888. Fair Candy Swap
Problem Description
Alice and Bob each have a collection of candy boxes, with each box containing a certain number of candies. The total number of candies each of them has is different. Given two lists, aliceSizes
representing the number of candies in Alice's boxes and bobSizes
for Bob's boxes, the task is to find a pair of boxes (one from Alice and one from Bob) that they can exchange with each other so that they end up with the same total number of candies.
In other words, we need to find two values, one from each list, such that when Alice gives Bob the box with her value and Bob gives Alice the box with his value, the total candies they each have will be equal. The problem ensures that there is at least one such pair and asks us to return any one of them as a 2-element array: [Alice's box of candies, Bob's box of candies].
Intuition
The solution to this problem relies on the concept of the exchange itself and the resulting equality of candy totals for Alice and Bob. If x
is the amount of candies in the box Alice gives to Bob, and y
is the amount in the box Bob gives to Alice, after the exchange, the total candies for both should be the same. If we denote sumA
as the total candies that Alice has and sumB
for Bob, the equation after the exchange would be:
(sumA - x) + y = (sumB - y) + x
Which can be simplified to:
sumA - sumB = 2 * (x - y)
By rearranging the terms, we get the difference diff
between the totals divided by 2 equals the difference between x
and y
:
diff = sumA - sumB
x - y = diff / 2
Given this, we can then iterate through Alice's boxes, and for each candy count a
, we can calculate the corresponding count target = a - diff / 2
that we're looking for in Bob's boxes. Then by utilizing a Set in Python that contains all of Bob's candy box counts, we can quickly check whether this target
exists. Because Set operations in Python are O(1) on average, this check is efficient.
If we find a match (target
in Bob's Set), we return that pair [a, target]
as our solution.
Learn more about Binary Search and Sorting patterns.
Solution Approach
The fairCandySwap
algorithm takes two lists of integers as input: aliceSizes
and bobSizes
. Each list represents the sizes of candy boxes for Alice and Bob, respectively.
The approach starts by calculating the difference in total candy amounts between Alice and Bob and dividing it by 2. The division by 2 comes from rearranging the equation sumA - sumB = 2 * (x - y)
into x - y = (sumA - sumB) / 2
. This value is stored in the variable diff
, signifying the amount of candy that needs to be compensated for in the swap to balance the totals:
1diff = (sum(aliceSizes) - sum(bobSizes)) >> 1
In the code, the right-shift operator >> 1
is used as an efficient way to divide the difference by 2.
Next, a Set called s
is created from Bob's list of candy sizes. Sets allow for constant time complexity (O(1)) checks for the existence of an element, which is leveraged later:
1s = set(bobSizes)
The algorithm then iterates through the list of Alice's candy sizes. For each candy size a
, it computes the corresponding candy size target
that Bob needs to provide:
1for a in aliceSizes: 2 target = a - diff 3 if target in s: 4 return [a, target]
This loop checks whether the calculated target
exists in Bob's set of candy sizes (s
). If it does, that means there is a pair of candy boxes [a, target]
that can be swapped to ensure both Alice and Bob end up with the same total amount of candy. The algorithm then returns this pair as soon as it's found.
In summary, the algorithm follows these steps:
- Calculate the difference
diff
between Alice's and Bob's total candy amounts and divide it by 2. - Create a Set from Bob's candy sizes for efficient lookup.
- Iterate through Alice's candy sizes, calculate the corresponding
target
size for Bob. - Check if
target
exists in Bob's Set. - Return the first pair
[a, target]
wheretarget
is in Bob's Set.
This approach leverages arithmetic to determine the needed exchange and a Set for efficient lookup, making the solution both straightforward and performant.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following candy box sizes for Alice and Bob:
aliceSizes = [1, 2, 5]
bobSizes = [2, 4]
Here's how we would use the solution approach to find the pair of boxes to be exchanged:
-
Calculate the total candies and the difference
diff
:We sum up the candies in Alice's and Bob's boxes:
sumA = 1 + 2 + 5 = 8
sumB = 2 + 4 = 6
Therefore, the difference
diff = (sumA - sumB) / 2 = (8 - 6) / 2 = 1
. -
Create a Set of Bob's candy sizes for efficient lookup:
s = set(bobSizes)
, which gives uss = {2, 4}
. -
Iterate through Alice's candy sizes to find the corresponding target for Bob:
For
a
in[1, 2, 5]
, we calculatetarget
as follows:- When
a = 1
,target = 1 - diff = 1 - 1 = 0
. Since0
is not in sets
, we continue. - When
a = 2
,target = 2 - diff = 2 - 1 = 1
. Since1
is not in sets
, we continue. - When
a = 5
,target = 5 - diff = 5 - 1 = 4
.4
is in sets
.
- When
-
Return the first successful pair
[a, target]
:Since we found
4
(which istarget
) in Bob's set when Alice's box size was5
, the pair[5, 4]
is returned.
So, by utilizing the solution approach, we find that Alice can give Bob a box of 5
candies, and Bob can give Alice a box of 4
candies, and they will both end up with 7
candies total, achieving a fair candy swap.
Solution Implementation
1class Solution:
2 def fairCandySwap(self, alice_sizes: List[int], bob_sizes: List[int]) -> List[int]:
3 # Compute the difference in candy sizes between Alice and Bob, divided by 2
4 # because any swap should compensate for half of the total size difference.
5 size_difference = (sum(alice_sizes) - sum(bob_sizes)) // 2
6
7 # Create a set of Bob's candy sizes for constant-time look-up
8 bob_sizes_set = set(bob_sizes)
9
10 # Iterate through Alice's candy sizes to find the fair swap
11 for candy_size_alice in alice_sizes:
12 # Calculate the target size of Bob's candy that would make the swap fair
13 target_size_bob = candy_size_alice - size_difference
14
15 # Check if Bob has a candy of the target size
16 if target_size_bob in bob_sizes_set:
17 # Return a list containing Alice's candy size and the corresponding
18 # Bob's candy size for a fair swap
19 return [candy_size_alice, target_size_bob]
20
21 # Note: no need for an explicit return statement for no match scenario
22 # because the question implies there is always a valid swap.
23
1class Solution {
2
3 // Method to find the fair candy swap between Alice and Bob
4 public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
5 int sumAlice = 0, sumBob = 0; // Initialize sums of Alice's and Bob's candies
6 Set<Integer> bobCandies = new HashSet<>(); // Create a set to store Bob's candy sizes
7
8 // Calculate sum of candies for Alice
9 for (int candySize : aliceSizes) {
10 sumAlice += candySize;
11 }
12
13 // Calculate sum of candies for Bob and populate the set with Bob's candy sizes
14 for (int candySize : bobSizes) {
15 bobCandies.add(candySize);
16 sumBob += candySize;
17 }
18
19 // Compute the difference to be balanced, divided by 2
20 int balanceDiff = (sumAlice - sumBob) >> 1;
21
22 // Iterate through Alice's candies to find the fair swap
23 for (int aliceCandySize : aliceSizes) {
24 int targetSize = aliceCandySize - balanceDiff;
25 // Check if Bob has the candy size that would balance the swap
26 if (bobCandies.contains(targetSize)) {
27 // Return the pair that represents the fair swap
28 return new int[]{aliceCandySize, targetSize};
29 }
30 }
31
32 // If no fair swap is possible, return null
33 return null;
34 }
35}
36
1#include <vector> // Include necessary library for vector usage
2#include <numeric> // Include library for accumulate function
3#include <unordered_set> // Include library for unordered_set
4
5class Solution {
6public:
7 // Method to find a fair swap of candies between Alice and Bob
8 vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
9 // Calculate the total sum of candies Alice has.
10 int aliceCandySum = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
11 // Calculate the total sum of candies Bob has.
12 int bobCandySum = accumulate(bobSizes.begin(), bobSizes.end(), 0);
13
14 // Calculate the difference between Alice's and Bob's candy sums divided by 2.
15 int sizeDifference = (aliceCandySum - bobCandySum) / 2;
16
17 // Create a set for Bob's candy sizes for efficient look-up.
18 unordered_set<int> bobSizeSet(bobSizes.begin(), bobSizes.end());
19
20 // Store the answer in a vector.
21 vector<int> result;
22
23 // Iterate through Alice's candy sizes to find a matching size in Bob's set.
24 for (int aliceCandy : aliceSizes) {
25 // The target size for Bob that would balance the swap.
26 int targetSize = aliceCandy - sizeDifference;
27
28 // If the target size is in Bob's set, a fair swap is possible.
29 if (bobSizeSet.count(targetSize)) {
30 result = vector<int>{aliceCandy, targetSize};
31 break; // Found the correct swap, exit the loop.
32 }
33 }
34
35 return result; // Return the pair representing a fair swap.
36 }
37};
38
1function fairCandySwap(aliceCandySizes: number[], bobCandySizes: number[]): number[] {
2 // Calculate the sum of candies for both Alice and Bob.
3 let sumAlice = aliceCandySizes.reduce((accumulated, current) => accumulated + current, 0);
4 let sumBob = bobCandySizes.reduce((accumulated, current) => accumulated + current, 0);
5
6 // Calculate the difference in candies between Alice and Bob, divided by 2.
7 let halfDiff = (sumAlice - sumBob) >> 1;
8
9 // Create a set from Bob's candy sizes for constant-time lookups.
10 let bobSizesSet = new Set(bobCandySizes);
11
12 // Loop through each of Alice's candy sizes to find a fair swap.
13 for (let aliceCandy of aliceCandySizes) {
14 // Calculate the target size for Bob that would equalize the sum.
15 let targetBobCandy = aliceCandy - halfDiff;
16
17 // Check if the target candy size exists in Bob's collection.
18 if (bobSizesSet.has(targetBobCandy)) {
19 // If found, return the pair of candy sizes for Alice and Bob.
20 return [aliceCandy, targetBobCandy];
21 }
22 }
23
24 // If no fair swap is found, return an empty array.
25 // (The problem statement assures a solution always exists, so this line is never expected to be reached in practice.)
26 return [];
27}
28
Time and Space Complexity
Time Complexity: The time complexity of the given code is O(A + B)
, where A
is the number of elements in aliceSizes
and B
is the number of elements in bobSizes
. Here's the breakdown: calculating the sum of both arrays takes O(A)
and O(B)
time respectively; creating the set s
of bobSizes
takes O(B)
time; and the for loop runs for every element in aliceSizes
, giving another O(A)
. Since set look-up is O(1)
on average, checking if target
is in s
does not significantly add to the complexity. Thus, the overall time complexity is the sum of these operations, which simplifies to O(A + B)
.
Space Complexity: The space complexity of the code is O(B)
. This is because we create a set s
consisting of all elements in bobSizes
, which takes up space proportional to the number of elements in bobSizes
. No other significant space is used as the rest of the variables use constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we