Problem

Problem ID: 1073

Title: Adding Two Negabinary Numbers

Difficulty: Medium

Description:

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.

Thoughts

I would classify this question as a iykyk kind of question as it hard to encounter for the case for negative number (ie: -1)

Solution

Intuition:

• If both bit are set at the current bit index, it would borrow from the next bit. Irregardless if the current \((-2)^{i}\) is negative

  \[1*(-2)^i + 1*(-2)^i = -(-2)^{i+1}\]
• This is also similar if both the current bit index are set and there is carry from the previous.
• From the previous two points it should be obvious that the carry will minus from the next value instead of borrowing.

• The difficult part is when the bits and the sum adds up to \(-1\). The following identity could be used.

  \[-1 = 1*(-2)^0 + 1*(-2)^2\]

Implementation

class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        vector<int> ret;
        int arr1_i = arr1.size() - 1;
        int arr2_i = arr2.size() - 1;
        int carry = 0;
        
        
        while (arr1_i >= 0 || arr2_i >= 0 || carry != 0) {
            int arr1_bit = arr1_i >= 0 ? arr1[arr1_i] : 0;
            int arr2_bit = arr2_i >= 0 ? arr2[arr2_i] : 0;
            int sum = carry + arr1_bit + arr2_bit;
            int ret_bit = sum & 1;
            carry = -(sum >> 1);
            ret.push_back(ret_bit);
            arr1_i--;
            arr2_i--;
        }
        
        if (carry > 0) ret.push_back(carry);
        while (ret.size() > 1 && ret.back() == 0) ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};