### ndatta's blog

By ndatta, history, 4 years ago, ,

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.

• +4

 » 4 years ago, # |   0 Auto comment: topic has been updated by ndatta (previous revision, new revision, compare).
 » 4 years ago, # |   +3 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.
•  » » 4 years ago, # ^ |   0 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 :( !!
 » 4 years ago, # |   +3 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 X if you shift all bits to the left (towards greater powers) you will get  - 2·X. If you add bit-by-bit  - 2·X and X you will get  - X which 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 -> 011So iterate lower to higher bits and apply these two substitution rules when necessary.
•  » » 4 years ago, # ^ |   0 I got it :) Thanks a lot