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:

• 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

• 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.

Unable to solve this problem. Please help.

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

StackExchange Computer Science Q#109336, answer score: 2