888. Fair Candy Swap #

Problem #

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.

Example 1:

Input: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]
Output: [5,4]

Note:

• 1 <= A.length <= 10000
• 1 <= B.length <= 10000
• 1 <= A[i] <= 100000
• 1 <= B[i] <= 100000
• It is guaranteed that Alice and Bob have different total amounts of candy.
• It is guaranteed there exists an answer.

Problem Summary #

Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th candy bar that Alice has, and B[j] is the size of the j-th candy bar that Bob has. Since they are friends, they want to exchange one candy bar 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 the 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 that an answer exists.

Note:

• 1 <= A.length <= 10000
• 1 <= B.length <= 10000
• 1 <= A[i] <= 100000
• 1 <= B[i] <= 100000
• It is guaranteed that Alice and Bob have different total amounts of candy.
• An answer is guaranteed to exist.

Solution Ideas #

• The two people exchange candy so that their amounts of candy are equal. The task is to output an array containing the sizes of the candies each person must exchange.
• First, this problem guarantees that a solution exists, and second, only one exchange is allowed. With these two premises, the problem becomes easy. First calculate the amount of candy diff that A needs to gain or lose so that after the exchange the two have the same amount of candy. Then traverse B and check whether there is an element in A such that after B makes the corresponding exchange by diff, the two people’s candy amounts are equal. (The premise of this problem guarantees that one can be found.) Finally, output this element in A and the current element in B, which are the candy sizes the two people should exchange.

Code #

package leetcode

func fairCandySwap(A []int, B []int) []int {
	hDiff, aMap := diff(A, B)/2, make(map[int]int, len(A))
	for _, a := range A {
		aMap[a] = a
	}
	for _, b := range B {
		if a, ok := aMap[hDiff+b]; ok {
			return []int{a, b}
		}
	}
	return nil
}

func diff(A []int, B []int) int {
	diff, maxLen := 0, max(len(A), len(B))
	for i := 0; i < maxLen; i++ {
		if i < len(A) {
			diff += A[i]
		}
		if i < len(B) {
			diff -= B[i]
		}
	}
	return diff
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}