Fair Candy Swap - Practice Coding Problems

Fair Candy Swap - Problem

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 i-th box of candy that Alice has and bobSizes[j] is the number of candies of the j-th 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.

Input & Output

Example 1 — Basic Exchange

$ Input: aliceSizes = [1,1], bobSizes = [2,2]

› Output: [1,2]

💡 Note: Alice has total 2, Bob has total 4. If Alice gives 1 and gets 2, she has 1+2=3. If Bob gives 2 and gets 1, he has 4-2+1=3. Both end up with 3 candies.

Example 2 — Multiple Options

$ Input: aliceSizes = [1,2], bobSizes = [2,3]

› Output: [1,2]

💡 Note: Alice sum=3, Bob sum=5. Alice gives 1, gets 2 → Alice: 3-1+2=4. Bob gives 2, gets 1 → Bob: 5-2+1=4. Equal totals achieved.

Example 3 — Larger Arrays

$ Input: aliceSizes = [2,1,1], bobSizes = [1,2,3]

› Output: [1,3]

💡 Note: Alice sum=4, Bob sum=6. Alice gives 1, gets 3 → Alice: 4-1+3=6. Bob gives 3, gets 1 → Bob: 6-3+1=4. Wait, that's not equal. Let me recalculate: Alice gives 1, gets 2 → Alice: 4-1+2=5. Bob gives 2, gets 1 → Bob: 6-2+1=5.

Constraints

1 ≤ aliceSizes.length, bobSizes.length ≤ 10⁴
1 ≤ aliceSizes[i], bobSizes[i] ≤ 10⁵
Alice and Bob have different total amounts of candy
At least one valid exchange exists

Visualization

Tap to expand

Understanding the Visualization

Input

Alice has [1,1] (total=2), Bob has [2,2] (total=4)

Exchange

Alice gives 1 candy box, Bob gives 2 candy box

Result

Both end up with total=3 candies

Key Takeaway

🎯 Key Insight: Use the mathematical relationship that Alice must give exactly (her_total - his_total) / 2 more than she receives to balance the exchange.

Asked in

G Google 15 a Amazon 8 f Facebook 5

The key insight is using the mathematical formula: for equal exchange, Alice must give Bob exactly (AliceSum - BobSum) / 2 more candies than she receives. The hash set approach is optimal with O(n+m) time and O(m) space, much better than the brute force O(n×m) solution.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n×m)	O(1)	Check every possible pair of boxes that Alice and Bob could exchange
Hash Set Optimization	O(n + m)	O(m)	Use math formula to find required exchange value, then hash lookup

Brute Force - Try All Combinations — Algorithm Steps

Calculate Alice's and Bob's current totals
For each Alice box, try exchanging with each Bob box
Check if exchange results in equal totals
Return the first valid exchange found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Sums

Find Alice's total (7) and Bob's total (5)

Try Each Pair

Check if exchanging Alice[i] with Bob[j] balances totals

Found Match

Alice gives 1, Bob gives 2 → both have 6

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* aliceSizes, int aliceLen, int* bobSizes, int bobLen, int* result) {
    int aliceSum = 0, bobSum = 0;
    for (int i = 0; i < aliceLen; i++) aliceSum += aliceSizes[i];
    for (int i = 0; i < bobLen; i++) bobSum += bobSizes[i];
    
    for (int i = 0; i < aliceLen; i++) {
        for (int j = 0; j < bobLen; j++) {
            int alice = aliceSizes[i];
            int bob = bobSizes[j];
            int newAliceSum = aliceSum - alice + bob;
            int newBobSum = bobSum - bob + alice;
            if (newAliceSum == newBobSum) {
                result[0] = alice;
                result[1] = bob;
                return;
            }
        }
    }
}

int parseArray(char* s, int* arr) {
    int len = 0;
    char* token = strtok(s + 1, ",]");
    while (token != NULL) {
        arr[len++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    return len;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int aliceSizes[100], bobSizes[100];
    int aliceLen = parseArray(line1, aliceSizes);
    int bobLen = parseArray(line2, bobSizes);
    
    int result[2];
    solution(aliceSizes, aliceLen, bobSizes, bobLen, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Nested loops: n Alice boxes × m Bob boxes

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

980 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler