[LeetCode] 888. Fair Candy Swap [Python] math

leetcode.com/problems/fair-candy-swap/

Fair Candy Swap - LeetCode

Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar 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 sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them.  It is guaranteed an answer exists.

 

 

Alice와 Bob이 같은 양의 캔디를 가지기 위해서 서로 바꿔야 되는 캔디바를 찾는 문제이다.

Input: A = [1,2,5], B = [2,4] Output: [5,4] 에서 엘리스가 가진 5와 밥이 가진 4를 서로 바꾸면 엘리스와 밥은 7개씩 똑같은 갯수의 캔디를 가질수 있다.

 

사실 이 문제는 간단한 수학문제이다. 엘리스와 밥이 가지고있는 캔디의 수를 모두 더해서 반으로 나누고, 그 나눈 값을 만들수 있는 숫자를 밥과 엘리스의 어레이에서 찾으면 된다. 이를 가지고 식을 세우면, Sum(A) - a + b = Sum(B) - b + a 이 된다 (a와 b는 list A와 B의 element이다). element a from A 를 찾는 식으로 다시한번 정리하면, a = (Sum(A) - Sum(B))/2 + b가나온다. 이를 그대로 코드로 옮겨적어 계산하면 끝! 해당 솔루션은 런타임 O(n)이 나온다. 

---

class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        avg = (sum(A) - sum(B)) // 2
        A = set(A)
        for b in B:
            if avg + b in A:
                return [avg + b, b]

---