We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Fair Candy Swap

Number: 924

Difficulty: Easy

Paid? No

Companies: Google, Swiggy, Amazon, Adobe, Yahoo

Problem Description

Alice and Bob each have boxes of candy represented by two arrays. They want to swap exactly one box each so that after the exchange, both have the same total number of candies. Return the pair of candy counts (one from Alice and one from Bob) that will achieve this equality.

Key Insights

  • Compute the sum of candies for both Alice and Bob.
  • Let diff = (sumBob - sumAlice) / 2. This represents the extra candy count Bob has per swap.
  • For a valid swap, if Alice gives a candy box with count a, then Bob must give a candy box with count a + diff.
  • Use a set for Bob’s candies to quickly check for existence.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. Space Complexity: O(m), as we store Bob's candy sizes in a set.

Solution

We start by calculating the total candies Alice and Bob have. To balance the swap, we derive that for any candy count a in Alice's collection, Bob must have a candy count equal to a + diff, where diff is (sumBob - sumAlice) / 2. Using a set for Bob's candy sizes allows constant time checks for whether a suitable candidate exists. We then iterate through Alice's list and return the first valid pair we find.

Code Solutions

# Calculate the total candies for Alice and Bob
def fairCandySwap(aliceSizes, bobSizes):
    # Compute the sum of candies for Alice and Bob
    sum_alice = sum(aliceSizes)
    sum_bob = sum(bobSizes)
    
    # The difference that must be compensated by the swap
    diff = (sum_bob - sum_alice) // 2
    
    # Store bob's candy sizes in a set for O(1) lookup
    bob_set = set(bobSizes)
    
    # For each candy count in Alice's sizes, check if bob has the required candy count
    for candy in aliceSizes:
        # The candy count that Bob must have for a fair swap with this candy box
        if candy + diff in bob_set:
            return [candy, candy + diff]

# Example usage:
print(fairCandySwap([1,1], [2,2]))  # Expected output: [1,2]
← Back to All Questions