Binary Addition Base -2

Easy
0/40
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in companies
Cerner CorporationCitrix

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3 3
1 0 1
1 0 1
3 1
1 0 0
1
Sample Output 1:
1 1 1 1 0
1 0 1
Explanation For Sample Input 1:
In the first test case, 
(101) base - 2  = ( 5 ) base 10
(11110) base  -2 = ( (-2) ^ 4 + (-2) ^ 3 + (-2) ^ 2 + (-2) ^ 1 ) = ( 10 ) base 10 
As, 5 + 5 = 10 

In the second test case, adding 4 with 1 will give 5.
Sample Input 2:
2
1 1
0
0
1 1
1
1
Sample Output 2:
0
1 1 0
Explanation For Sample Input 2:
In the first test case, adding 0 with 0 will give 0. 

In the second test case, adding 1 with 1 will give 2 (4 - 2).
Hint

Can you think of solving this problem the same as we add two decimal numbers?

Approaches (1)
Simulating the process

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:

 

  1. We will use the variable ‘CARRY’ initialized to 0 to maintain the carry of our sum.
  2. Create a deque ‘ANS’ that will store the final answer.
  3. 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.
  4. After adding all the bits there might be some ‘CARRY’ remaining. Append the bits of the ‘CARRY’ at the beginning of our ‘ANS’.
  5. We will remove all the leading ‘0’ bits from the ‘ANS’.
  6. Return the ‘ANS’.
Time Complexity

O(N + M), where ‘N’ is the length of ‘ARR1’ and ‘M’ is the length of ‘ARR2’.

 

We will pop each bit from ‘ARR1’ and ‘ARR2’ exactly once. So, the overall time complexity will be O(N + M).

Space Complexity

O(N + M), where ‘N’ is the length of ‘ARR1’ and ‘M’ is the length of ‘ARR2’.

 

Since we are using extra space to hold the final answer and we know that our answer will have bits comparable to 'N + M' and so, the overall space complexity will be O(N + M).

Code Solution
(100% EXP penalty)
Binary Addition Base -2
Full screen
Console