Skip to content

888. Fair Candy Swap 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
    const int diff = (accumulate(aliceSizes.begin(), aliceSizes.end(), 0) -
                      accumulate(bobSizes.begin(), bobSizes.end(), 0)) /
                     2;
    const unordered_set<int> bobSizesSet{bobSizes.begin(), bobSizes.end()};

    for (const int aliceSize : aliceSizes) {
      const int target = aliceSize - diff;
      if (bobSizesSet.count(target))
        return {aliceSize, target};
    }

    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
    final int diff = (Arrays.stream(aliceSizes).sum() - Arrays.stream(bobSizes).sum()) / 2;
    Set<Integer> bobSizesSet = Arrays.stream(bobSizes).boxed().collect(Collectors.toSet());

    for (final int aliceSize : aliceSizes) {
      final int target = aliceSize - diff;
      if (bobSizesSet.contains(target))
        return new int[] {aliceSize, target};
    }

    throw new IllegalArgumentException();
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
    diff = (sum(aliceSizes) - sum(bobSizes)) // 2
    bobSizesSet = set(bobSizes)

    for aliceSize in aliceSizes:
      target = aliceSize - diff
      if target in bobSizesSet:
        return [aliceSize, target]