1073. Adding Two Negabinary Numbers

1073. Adding Two Negabinary Numbers (Medium)

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.

Example 2:

Input: arr1 = [0], arr2 = [0]
Output: [0]

Example 3:

Input: arr1 = [0], arr2 = [1]
Output: [1]

 

Constraints:

• 1 <= arr1.length, arr2.length <= 1000
• arr1[i] and arr2[i] are 0 or 1
• arr1 and arr2 have no leading zeros

Companies:
Grab

Related Topics:
Array, Math

Solution 1.

When adding two numbers in base 2 I use a variable carry to store the carryover.

Assume we are adding two bits a, b and carry. The sum can be 0, 1, 2, 3, and the leftover bit value is sum % 2 and the new value of carry is sum / 2.

Let's try the same approach for this problem.

Assume the current bit represents k = (-2)^n, (n >= 0).

• Consider carry = 0, sum can be 0, 1, 2.
  • When sum = 0 or 1, leftover = sum, carry = 0.
  • When sum = 2, the value is 2k = -1 * (-2k), so it's the same as leftover = 1, carry = -1
• Consider carry = -1, sum can be -1, 0, 1.
  • For the new case sum = -1, the value is -k = -2k + k, so it's the same as leftover = 1, carry = 1.
• Consider carry = 1, sum can be 1, 2, 3.
  • For the new case sum = 3, the value is 3k = -1 * (-2k) + k, so it's the same as leftover = 1, carry = -1.

Now we've considerred all cases. In sum:

sum	leftover	carry
-1	1	1
0	0	0
1	1	0
2	0	-1
3	1	-1

The pattern is:

leftover = (sum + 2) % 2
carry = 1 - (sum + 2) / 2

Or

leftover = sum & 1
carry = -(sum >> 1)

// OJ: https://leetcode.com/problems/adding-two-negabinary-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> addNegabinary(vector<int>& A, vector<int>& B) {
        vector<int> ans;
        for (int i = A.size() - 1, j = B.size() - 1, carry = 0; i >= 0 || j >= 0 || carry;) {
            if (i >= 0) carry += A[i--];
            if (j >= 0) carry += B[j--];
            ans.push_back(carry & 1);
            carry = -(carry >> 1);
        }
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Solution 2.

Add the two numbers first without any carry over into any array ans.

If ans[i] >= 2:

• If ans[i+1] != 0, we do ans[i] -= 2 and ans[i+1]--
• Otherwise, we do ans[i] -= 2 and ans[i+1]++, ans[i+2]++.

// OJ: https://leetcode.com/problems/adding-two-negabinary-numbers/
// Author: github.com/lzl124631x
// Time: O()
// Space: O()
class Solution {
public:
    vector<int> addNegabinary(vector<int>& A, vector<int>& B) {
        int carry = 0;
        vector<int> ans;
        for (int i = A.size() - 1, j = B.size() - 1; i >= 0 || j >= 0;) {
            ans.emplace_back();
            if (i >= 0) ans.back() += A[i--];
            if (j >= 0) ans.back() += B[j--];
        }
        for (int i = 0; i < ans.size(); ++i) {
            if (ans[i] < 2) continue;
            ans[i] -= 2;
            if (i + 1 == ans.size()) ans.emplace_back();
            if (i + 2 == ans.size()) ans.emplace_back();
            if (ans[i + 1]) ans[i + 1]--;
            else ans[i + 1]++, ans[i + 2]++;
        }
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        reverse(begin(ans), end(ans));
        return ans;
    }
};