2s complement | Commented and Explained | Convert from -2 base then convert back
Intuition\n Describe your first thoughts on how to solve this problem. \nWe want to first know what values we have \nThen, we want to know what we sum up to \nT
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to first know what values we have \nThen, we want to know what we sum up to \nThen, we want to convert from where we are to where we want to go \nWe can do this with two functions and a few calls as detailed below. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst we build our convert from negative form function \nThis function takes in an array to convert that is assumed to be in base -2. We have no way to check that in the current problem, so we take it on faith. Then, the following occurs \n- Our place value starts in the 1s place for any base (as anything to the power of 0, even a negative base, is 0) \n- Our return valuation starts at 0, and we will adjust from there \n- Then, we reverse our array (could also chose to read from the back, but good to call it when it occurs for readability) \n- Then, for bit in array to convert \n    - return valuation is incremented by the product of the bit with the place value \n    - place value is incremented as the product of itself with -2 \nWhen done, return return valuation \n\nNow that we have that, we get the array valuations \nDo this for array 1 and array 2 and make sure they match by hand. I have removed the print statements, but you could print these out after and then check. Once this is working correctly, we sum these valuations up as sum of arrays. \n\nNow we build our convert to negative form function which is given a value to convert and returns an array in base -2. To do so, we do the following\n- if value to convert is 0, return [0]\n- otherwise, set a negative form array as a deque\n- while your value to convert is not zero (meaning we are out of material)\n    - update value to convert and get the remainder from the update as the result of a call to divmod, passing in value to convert and -2 as arguments\n    - if our remainder is less than 0, it must be -1. \n    - if our remainder is negative 1 \n        - our value to convert is 1 greater than before (carry operation)\n        - remainder then is set to 1 \n    - append the remainder to the front of the negative form array \n- when done, we have our array, return it \n\n# Complexity\n- Time complexity: O(N) \n    - each array is converted \n    - the summation is converted back \n    - both take linear time  \n\n\n- Space complexity: O(N) \n    - we end up creating an array to store the solution of size O(N) \n\n# Code\n```\n"""\n    array valuation example walkthrough \n    for the first problem, we are given \n    [1, 1, 1, 1, 1]\n    and \n    [1, 0, 1]\n\n    If we evaluate the converted form of these, the first is 11 and the second is 5 \n    This gives a form of 16 in base of -2 \n    in base of -2, 16 is -2^4 \n    Remembering that we start at power 0, this as an array is then \n    [1, 0, 0, 0, 0]\n\n    Where we can notice that even powers of -2 will be the same as the regular powers of positive 2 \n    This should come as no surprise if you have studied 2\'s complement which the problem is based on\n    Learn more here : https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html \n\n"""\n\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        # converts from negative binary form array to a valuation\n        def convert_from_negative_form(array_to_convert) : \n            place_value = 1\n            return_valuation = 0\n            array_to_convert.reverse()\n            for bit in array_to_convert : \n                return_valuation +=  bit * place_value \n                place_value *= -2\n            return return_valuation\n\n        # get array valuations \n        array_1_valuation = convert_from_negative_form(arr1)\n        array_2_valuation = convert_from_negative_form(arr2)\n        # sum them \n        sum_of_arrays = array_1_valuation + array_2_valuation\n        \n        # converts from value to convert to array form in 2s complement form \n        def convert_to_negative_form(value_to_convert) : \n            # base case \n            if value_to_convert == 0 : \n                return [0]\n            # set up for return \n            negative_form_array = collections.deque()\n            # build negative_form_array while not 0 \n            while value_to_convert != 0 : \n                # update value to convert \n                value_to_convert, remainder = divmod(value_to_convert, -2)\n                # remainder is either -1 or 0 \n                # if it is 0 we\'re good, \n                # but if not we need to account for overflow \n                if remainder < 0 : \n                    # shift value to convert forward on remainder -1 \n                    value_to_convert += 1 \n                    # cannot place -1 in binary array, but can place 1\n                    remainder = 1\n                # append remainder as this is the 2s complement left over \n                negative_form_array.appendleft(remainder)\n            # return when done \n            return negative_form_array \n\n        # get valuation \n        negative_array = convert_to_negative_form(sum_of_arrays)\n        # return negative array \n        return negative_array \n```
['Python3']