Converting a number from N to 0 in binary

Trying to solve this problem since 2 days. Still unable to figure out even a basic approach.

Given a number $$N$$ in binary ($$1$$ to $$10^5$$), we need to convert it to $$0$$ using only 2 operations. Given a binary value of a number with length $$M$$ ($$0$$ indexed), we can:

1. flip the $$i$$th bit from $$0$$ to $$1$$ or $$1$$ to $$0$$ only if the $$(i+1)$$th bit is 1 and all bits at positions from $$i+2$$ to $$M-1$$ are NOT $$1$$, or
2. flip the rightmost bit unconditionally.

So the problem is to figure out the minimum number of steps to do the conversion.

For example: if $$N=8$$, then its binary representation is $$1000$$.

So to convert $$1000$$ to $$0000$$, the following steps apply:

1 -  1001 (flipping the rightmost bit unconditionally).
2 -  1011 (flipping bit at position 2 as bit at position 3 = 1 and there are no more 1 after it. There are no more characters infact. It is the last character).
3  - 1010 (flipping the rightmost bit unconditionally).
4  - 1110 (flipping the 1st bit as 2nd bit is 1 and no other bits after that are 1)
5  - 1111 (flipping the last bit unconditionally).
6  - 1101 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
7  - 1100 (flipping the last bit unconditionally).
8  - 0100 (flipping 0th bit as 1st bit is 1 and no other 1 after 1st bit).
9  - 0101 (flipping the last bit unconditionally).
10 - 0111 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
11 - 0110 (flipping the last bit unconditionally).
12 - 0010 (flipping 1st bit as 2nd bit is 1 and no other 1 after 2nd bit).
13 - 0011 (flipping last bit unconditionally).
14 - 0001 (flipping 2nd but as 3rd bit is 1 and no other bit after 3rd bit).
15 - 0000 (flipping last bit unconditionally).


So the result is $$15$$ as it took $$15$$ steps.

• It seems the two operations are actually the same. The second one is the same as the first one when $i$ is the LSB and you consider the condition on the bits $>i$ (of which there are none) to be vacuous. – dkaeae May 14 '19 at 15:00
• @Apass.Jack what? – Aditya Singh May 14 '19 at 18:29
• "consider a binary value of a number with length M (0 indexed)". Did you mean with length 1000 in the example? – John L. May 14 '19 at 19:12
• @Apass.Jack No. Just the length of the binary string (char array) is M. And the array is 0 indexed. – Aditya Singh May 14 '19 at 19:14
• "For example: If N=8. Then M=1000." Did you mean the binary representation of $8$ is 1000? Then it should be clearer if the symbol $M$ is not used here. – John L. May 14 '19 at 19:21

I think you can just do a simple breadth-first-search on this. First note that:

• There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop.
• It doesn't make sense to do move #2 twice in a row.

The important thing to do while searching is to note whether the number we've arrived at was by doing move #2 (otherwise we'd get stuck in a loop). So here's a pseudocode:

• Put the current number into a queue with flag 0

• While the dequeued number is not zero:

• If you can do move #1 on the dequeued number then do move #1 and put that in a queue with flag 0
• If the dequeued number's flag is 0, then do move #2, and put that in the queue with flag 1
• Hey! What if the dequeued number has flag 0 and I am still able to do move #1? Shall I do both moves and push them in the queue? How is it going to work with number 29? When N=29 and M=11101? – Aditya Singh May 14 '19 at 18:31
• The two if statements are not linked. If you can do both then you should enqueue both. – Art May 15 '19 at 0:05

First, we have some basic observations:

1. The minimum number of steps to convert $$N$$ to $$0$$ equals to the minimum number of steps to convert $$0$$ to $$N$$.

2. To convert $$0$$ to $$N$$, the optimal way would be to apply Operation 1 and 2 alternatively.

Now consider the bit sequence $$b_1\ldots b_m0$$. After performing Operation 1 and 2 alternatively, we get

$$b_1\ldots b_m0\rightarrow b_1\ldots b_m1\rightarrow c_1 \ldots c_m1\rightarrow c_1\ldots c_m0\rightarrow d_1\ldots d_m0\rightarrow d_1\ldots d_m1\rightarrow\cdots$$

where $$c_1\ldots c_m$$ is the bit sequence obtained by applying Operation 1 on $$b_1\ldots b_m$$ and $$d_1\ldots d_m$$ is the bit sequence obtained by applying Operation 2 on $$c_1\ldots c_m$$. Note every time we perform two operations, one operation is applied on the sequence of the first $$m$$ bits. That is to say, if we denote by $$f(x_1\ldots x_m)$$ the minimum number of steps to convert $$0\ldots 0$$ to $$x_1\ldots x_m$$, then we have

$$f(x_1\ldots x_m)=2f(x_1\ldots x_{m-1}) +\text{the number of the rest steps to convert the last bit to }x_m.$$

Easy to see the number of the rest steps to convert the last bit to $$x_m$$ depends on the parity of $$f(x_1\ldots x_{m-1})$$. If $$f(x_1\ldots x_{m-1})$$ is even, after performing $$2f(x_1\ldots x_{m-1})$$ operations, the last bit is $$0$$, so the number of the rest steps to convert the last bit to $$x_m$$ is exactly $$x_m$$. Otherwise, it is $$1-x_m$$.

Now it is sufficient to use the recurrence above to calculate the minimum number of steps to convert $$N$$ to $$0$$ in $$O(\log N)$$ time if you don't care the detailed operation sequence.

Finally, for fun, you can prove using mathematical induction:

$$f(x_1\ldots x_m)=x_12^{m-1}+(x_1\oplus x_2)2^{m-2}+(x_1\oplus x_2\oplus x_3)2^{m-3}+\cdots+(x_1\oplus\cdots\oplus x_m).$$