Bit Operation with little trick - Beat 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nthe list of binary will be different with usual binary, the negabinary representation w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nthe list of binary will be different with usual binary, the negabinary representation will be like this:\n[...,64,-32,16,-8,4,-2,1]\n\nif there is 1 + 1 (base 10), the result will be 2. on negabinary will be [1,1,0] = 4 + (-2) + 0 = 2\nso the answer of 1 + 1 = 110\n\nOR\n\nthe next bit is (- prevbit*2), we we have carry over and there is >= 1 bit on the next bit, we just substract it\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\ncalculate arr1 & arr2, iterating it from most left to the most right, if there is carry bit, we check on the next, if next bit is > 0, decrease it by -1, if not, adding next bit and next 2 bit by 1\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nfunc addNegabinary(arr1 []int, arr2 []int) []int {\n    if len(arr1) < len(arr2) {\n        arr1, arr2 = arr2, arr1\n    }\n    \n    for i := 0; i < len(arr2); i++ {\n        arr1[len(arr1)-i-1] += arr2[len(arr2)-i-1]\n    }\n\n    res := []int{}\n\n    for i := 0; i < len(arr1); i++ {\n        index := len(arr1)-i-1\n        curr := arr1[index]\n        arr1[index] %= 2\n        if curr <= 1 {continue}\n        if index-1 >= 0 && arr1[index-1] > 0 {\n            arr1[index-1]--\n        } else if index-2 >= 0 {\n            arr1[index-1]++\n            arr1[index-2]++\n        } else {\n            res = []int{1,1}\n        }\n    }\n\n    res = append(res, arr1...)\n    var i int\n    for i = 0; i < len(res); i++ {\n        if res[i] == 1 {break} \n    }\n    if len(res) == i {return []int{0}}\n    return res[i:]\n}\n```
['Go']