1073. Adding Two Negabinary Numbers

Problem

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1]represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Note:

1. 1 <= arr1.length <= 1000
2. 1 <= arr2.length <= 1000
3. arr1 and arr2 have no leading zeros
4. arr1[i] is 0 or 1
5. arr2[i] is 0 or 1

Problem Summary

Given two numbers arr1 and arr2 with base -2 , return the result of adding the two numbers. The numbers are given in array form ：the array consists of several 0s and 1s，arranged from the most significant bit to the least significant bit. For example，arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3。Numbers in array form also similarly contain no leading zeros：taking arr as an example，this means either arr == [0]，or arr[0] == 1。

Return the result of adding arr1 and arr2 in the same representation form. The representation form of the two numbers is：an array containing no leading zeros and consisting of several 0s and 1s。

Hint：

• 1 <= arr1.length <= 1000
• 1 <= arr2.length <= 1000
• arr1 and arr2 both contain no leading zeros
• arr1[i] is 0 or 1
• arr2[i] is 0 or 1

Solution Approach

• Given two base -2 numbers，it is required to calculate the sum of these two numbers，and the final representation form is still base -2。
• The first approach that comes to mind for this problem is to first convert the two base -2 numbers into base 10 and then perform addition，then represent the result in base -2。This approach is feasible，but after submitting it, you will find that the data overflows int64。WA will occur on the 257 / 267th set of test data。See the test file for the test data。In addition, switching to big.Add is also not very convenient。So consider changing to another approach。
• This problem is actually just finding the addition of two base -2 numbers，so why first convert to base 10 and then convert back to base -2？Why not directly perform base -2 addition。So start trying to directly perform addition operations。Addition accumulates sequentially from low bits to high bits，and when encountering a carry, it must carry from low to high bits。So scan forward from the end of the two arrays，simulating the process of adding low bits。The key is the carry problem。Carry is divided into 3 cases，discussed in order：

1. Carry to high bit k ，the two digits at high bit k are respectively 0 and 0 。In this case, the final k bit is 1 。

        Proof：Since the carry comes from bit k - 1，bit k - 1 has 2 1s 。Now bit k has 2 0s，
        So the sum is 2 * (-2)^(k - 1)。
        When k is odd，2 * (-2)^(k - 1) = (-1)^(k - 1)* 2 * 2^(k - 1) = 2^k
        When k is even，2 * (-2)^(k - 1) = (-1)^(k - 1)* 2 * 2^(k - 1) = -2^k
        Taken together, this is (-2)^k，so there is ultimately a 1 at bit k

2. Carry to high bit k ，the two digits at high bit k are respectively 0 and 1 。In this case, the final k bit is 0 。

        Proof：Since the carry comes from bit k - 1，bit k - 1 has 2 1s。Now bit k has 1 0 and 1 1,
        So the sum is (-2)^k + 2 * (-2)^(k - 1)。
        When k is odd，(-2)^k + 2 * (-2)^(k - 1) = -2^k + 2^k = 0
        When k is even，(-2)^k + 2 * (-2)^(k - 1) = 2^k - 2^k = 0
        Taken together, this is 0，so there is ultimately a 0 at bit k

3. Carry to high bit k ，the two digits at high bit k are respectively 1 and 1 。In this case, the final k bit is 1 。

        Proof：Since the carry comes from bit k - 1，bit k - 1 has 2 1s 。Now bit k has 2 1s，
        So the sum is 2 * (-2)^k + 2 * (-2)^(k - 1)。
        When k is odd，2 * (-2)^k + 2 * (-2)^(k - 1) = -2^(k + 1) + 2^k = 2^k*(1 - 2) = -2^k
        When k is even，2 * (-2)^k + 2 * (-2)^(k - 1) = 2^(k + 1) - 2^k = 2^k*(2 - 1) = 2^k
        Taken together, this is (-2)^k，so there is ultimately a 1 at bit k

• So in summary，the carry principle of base -2 and base 2 is completely consistent，except that the carry in base -2 is -1，while the carry in base 2 is 1 。Since carry may produce leading 0s in base -2 ，the final result needs to remove leading 0s again。

Code

package leetcode

// Solution One Simulate Carry
func addNegabinary(arr1 []int, arr2 []int) []int {
	carry, ans := 0, []int{}
	for i, j := len(arr1)-1, len(arr2)-1; i >= 0 || j >= 0 || carry != 0; {
		if i >= 0 {
			carry += arr1[i]
			i--
		}
		if j >= 0 {
			carry += arr2[j]
			j--
		}
		ans = append([]int{carry & 1}, ans...)
		carry = -(carry >> 1)
	}
	for idx, num := range ans { // remove leading 0s
		if num != 0 {
			return ans[idx:]
		}
	}
	return []int{0}
}

// Solution Two Standard simulation，but this method cannot AC，because the test data exceeds 64 bits，ordinary data types cannot store it
func addNegabinary1(arr1 []int, arr2 []int) []int {
	return intToNegabinary(negabinaryToInt(arr1) + negabinaryToInt(arr2))
}

func negabinaryToInt(arr []int) int {
	if len(arr) == 0 {
		return 0
	}
	res := 0
	for i := 0; i < len(arr)-1; i++ {
		if res == 0 {
			res += (-2) * arr[i]
		} else {
			res = res * (-2)
			res += (-2) * arr[i]
		}
	}
	return res + 1*arr[len(arr)-1]
}

func intToNegabinary(num int) []int {
	if num == 0 {
		return []int{0}
	}
	res := []int{}

	for num != 0 {
		remainder := num % (-2)
		num = num / (-2)
		if remainder < 0 {
			remainder += 2
			num++
		}
		res = append([]int{remainder}, res...)
	}
	return res
}