Given a number in base -2 in binary form. return negative of that number in base -2 in binary form. Given [1,0,0,1,1,1] => return [1,1,0,1,0,1,1]. [1,0,0,1,1,1] = -23 (from left) , neg(-23) = 23 in base -2, 23 is [1,1,0,1,0,1,1]. Length of the given array <= 10^5

Any idea? Thanks in advance.

Auto comment: topic has been updated by ndatta (previous revision, new revision, compare).One idea would be to look at the representations of a few small numbers, for example, +1 and -1, +2 and -2, ..., +10 and -10. You may be able to better understand what is going on just by looking at them.

Thanks for your reply. I tried but I found out only that positive numbers are of odd length and negative numbers are of even length. That's all :( !!

That is a problem I solved during pre-interview once. The key points to the solution:

Assuming you have this kind of bit representation of arbitrary

Xif you shift all bits to the left (towards greater powers) you will get - 2·X.If you add bit-by-bit - 2·

XandXyou will get -Xwhich is what you're looking for. But summing bits in naive way might produce some bit equal to 2 which is illegal.You need to get rid of number 2 in bit representation. So you need some rules to eliminate them. Below I show you two rules which are enough. I'll show them as string where characters to the right correspond to higher order bits.

a. 21 -> 00

b 20 -> 011

So iterate lower to higher bits and apply these two substitution rules when necessary.

I got it :) Thanks a lot