Adding Two Negabinary Numbers

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.

Solution: 

Negabinary numbers are numbers with base -2.
There are three basic rules for negabinary addition (base 10 equivalent in brackets)

• 1 (1) + 1(1) = 110 (2)
• 1 (1) + 1(1) + 1(1) = 111 (3)
• 11 (-1) + 1 (1) = 0 (0)

Let's see a step by step addition of numbers in the example above - 11111 + 101
Step 1:
Adding LSB, 1+1 = 110, we have carry = 11

Step 2:
Adding next LSB + carry

Step 3:
Adding next LSB + carry








Step 4:
Adding next LSB + carry

Step 5:
Adding next LSB + carry

Step 6:
Finally the carry is 11 (-1) + 1 (1) which is equal to 0.

Code :

	class Solution {
	public:
	vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
	reverse(arr1.begin(), arr1.end());
	reverse(arr2.begin(), arr2.end());
	vector<int> answer;
	int carry = 0;
	for (int i=0; i<arr1.size() || i<arr2.size()|| carry !=0; ++i){
	int x = (i<arr1.size() ? arr1[i] : 0) +
	(i<arr2.size() ? arr2[i] : 0) +
	carry;
	answer.push_back((x+2)%2);
	carry = (x-answer.back())/-2;
	}
	while(answer.size()>1 && answer.back()==0){
	answer.pop_back();
	}
	reverse(answer.begin(), answer.end());
	return answer;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub