3
$\begingroup$

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.

Unable to solve this problem. Please help.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dkaeae May 14 at 15:00
  • $\begingroup$ @Apass.Jack what? $\endgroup$ – Aditya Singh May 14 at 18:29
  • $\begingroup$ "consider a binary value of a number with length M (0 indexed)". Did you mean with length 1000 in the example? $\endgroup$ – Apass.Jack May 14 at 19:12
  • $\begingroup$ @Apass.Jack No. Just the length of the binary string (char array) is M. And the array is 0 indexed. $\endgroup$ – Aditya Singh May 14 at 19:14
  • $\begingroup$ "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. $\endgroup$ – Apass.Jack May 14 at 19:21
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Aditya Singh May 14 at 18:31
  • $\begingroup$ The two if statements are not linked. If you can do both then you should enqueue both. $\endgroup$ – Art May 15 at 0:05
1
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.