Convert Decimal to Negabinary — Learn from failure

A few days ago I had an algorithms assessment. I have a quite confidence that I would doing well on it since I have prepared enough with lots of time exercising in hackerrank and some other code-camp website.

In this challenge, I was given a sequence of 1 and 0 that need to be translated to number num, then I need to divide num by 2 (ceiling) and then convert the quotient to binary sequence, sounds easy isn’t it? :D, but all of them are made with base number -2. I was working on it the same as I was doing on usual binary with base 2 and only change the base with -2, and.. of course that didn’t work :D. I spent an hour working around to figure out how it should be done and I ran out of time.
I failed the test.

However, this failure did not disappoint me, this failure felt good. I feel challenged and spent a whole weekend to figure it out. I spent my time googling (but found nothing helpful), creating tables, figuring out the patterns, write off lots of line and repeating it all over again. and finally after a few works and naps. it came one eureka moment. A bulb was shining inside my head. I might fail the test but now I am thrilled that I have found the solution.

I realized that having -2 as a base will make a possibility for the remainder to be -1.
And that will not fulfill the requirement since the sequence should only contains 0 or 1.
It is a little bit tricky but here is explanation for whom interested or maybe having similar challenge.

Here is the task summary in more details.

Given an array B that contains sequence of N number as an input.
the sequence represent a number X that is equal to sum of B[i]*(-2)**i for i to N.
print out the sequence of number Y that represent the ceiling of X/2 in binary sequence with base -2.

First, we will look at the pattern of negabinary with base -2, see table below.
This table will be our reference to check the validity of the result generated from the code.

Task sample :

B = [1,0,0,1,1,1]

From the equation given in the task, we will get X = -23

So, Y = -12

Then, the sequence of negabinary should be [1,1,0,1,0,0]

Please note that the sequence of the output is in the reverse order compared to the input.

Solution:

make an iteration that divide X by -2 , the same as the operation for binary generator with base 2, but change 2 with -2 as the base.

Here we got [0, 0, -1, 1]. This does not match with the requirement (should only contain 1 or 0). So we need to do workaround.

Modification:

Quotient = quotient + 1

Remainder = remainder — divisor

Intermezzo:

Is it mathematically correct? We will look at other sample positive number to make it clear, let’s try with 7 and divisor 3.

7 = 3.2 + 1

But also equals to:

7 = 3.3 + (1–3)

7 = 9–2

We use this approach to make the remainder to be not -1.

Let’s go back to our problem. We could modify the operation from:

-3 = -2*1 + -1, Change it to:

-3 = -2*2 + 1

Then we can continue the operation. Thus we got table below:

Here we have another issue, the last quotient is -1. If we continue the operation, we will get another remainder = -1.

Now we need to implement again the modification approach above. So the final table will be:

Thus we have the negabinary sequence for -12 as: [0,0,1,0,1,1]

Reverse it and then we get the final result : [1,1,0,1,0,0]

And here is the function code in python that worked for the task.

"""
to_binary will convert the negabinary input array to decimal number X.
then it will divide X by 2 (ceiling) and return the negabinary sequence of Y
"""
def to_binary(A):
    num_input = sum([A[i]*(-2)**i for i in range(len(A))])
    print(num_input)
    num = num_input//2
    print(num)
    divisor = -2
    arr = []
    while num != 0:
        quotient, remainder = divmod(num, divisor)
        if remainder == -1:
            quotient += 1
            remainder -= divisor
            arr.append(remainder)
        else:
            arr.append(remainder)
        num = quotient
    return arr[::-1]

#for testing
if __name__ == "__main__":
    B = [1,1,1,0,0,1,1,1] #input your negabinary input here
    print(to_binary(B))