Last Updated: 17 Apr, 2021
Binary Addition Base -2
Easy
Asked in companies
You are given with the two binary arrays/lists ‘ARR1’ and ‘ARR2’ of size 'N' and 'M', representing two numbers in base -2. You have to find their addition in base -2.
Each array represents a base -2 number where index 0 represents the most significant bit of that number and the last index represents the least significant bit.
You have to find the addition of ‘ARR1’ and ‘ARR2’ and print the result as a binary array. The answer should not have any leading zeros.
Example :
‘ARR1’ = [1, 0, 1, 1], it represents (-2) ^ 3 + (-2) ^ 1 + (-2) ^ 0 = -9.
‘ARR2’ = [1, 0, 1] it represents (-2) ^ 2 + (-2) ^ 0 = 5.
‘RESULT’ = [1, 1, 0, 0], it represents (-2) ^ 3 + (-2) ^ 2 = -4.
As, -9 + 5 = -4.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N‘ and ‘M’, the number of bits in ‘ARR1’ and ‘ARR2’.
The second line of each test case contains ‘N’ space-separated bits, representing ‘ARR1’.
The third line of each test case contains ‘M’ space-separated bits, representing ‘ARR2’.
Output Format:
For each test case, print the addition of two numbers in base -2 representation.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N, M <= 10^6
Where ‘T’ is the number of test cases, 'N' is the length of ‘ARR1’ and 'M' is the length of ‘ARR2’.
Time Limit: 1 sec.
Approaches
Approach: We can add two base -2 numbers the same way as we add two base 10 numbers. We will go from least significant bit to most significant bit and maintain a carry.
The steps are as follows:
- We will use the variable ‘CARRY’ initialized to 0 to maintain the carry of our sum.
- Create a deque ‘ANS’ that will store the final answer.
- While 'ARR1'.size() and 'ARR2'.size() is not equal to 0:
- If there are bits in ‘ARR1’ we will pop the least significant bit and add it to the ‘CARRY’.
- If there are bits in ‘ARR2’ we will pop the least significant bit and add it to the ‘CARRY’.
- We will append the least significant bit of the carry at the beginning of our ‘ANS’.
- We will divide the ‘CARRY’ by -2.
- After adding all the bits there might be some ‘CARRY’ remaining. Append the bits of the ‘CARRY’ at the beginning of our ‘ANS’.
- We will remove all the leading ‘0’ bits from the ‘ANS’.
- Return the ‘ANS’.