2

You are provided a number X and another number Y.
You can apply only the following operations : -
a) If the number is even, either double the number or increase it by 1.
b) If the number is odd, either double the number or decrease it by 1.

What should be the minimum number of steps to convert X to Y?

For example - If $X = 4$, and $Y = 11$ , the answer is $3$.
$4\to 5\to 10\to 11$.

There can be cases where answer is not reachable at all like $X=4, Y=6$.

nonuser
  • 90,026
user249117
  • 245
  • One approach to such problems is as a shortest-path graph problem, the best known algorithm for which is Dijkstra's. Are you asking for an algorithm? – hardmath Sep 04 '17 at 20:06
  • The numbers can be as high as 10^18. Dijkstra or related approached won't work. Is there some binary operation related to it is my primary question. – user249117 Sep 04 '17 at 20:07
  • Think in terms of the bits required in the binary expansion of $|y-x|$. – Anurag A Sep 04 '17 at 20:08
  • I tried. Let's say X=4, Y=20. Y-X=16. Number of bits is just 1, but the answer is 3. 4->5->10->20 – user249117 Sep 04 '17 at 20:12
  • It seems to me that the number of bits in expressing $X$ cannot be decreased by more than one (if $X$ is odd, not at all if $X$ is even). – hardmath Sep 04 '17 at 20:13

2 Answers2

3

In binary, you can either toggle the least significant bit or append a 0 bit. Consequently, there is (up to loops) only one way to get from an $n$-bit number $X$ to an $m$-bit number $Y$:

  1. If $n>m$ or the first $n-1$ bits of $X$ differ from the first $n-1$ bits of $Y$, no solution is possible. Terminate
  2. ensure that the first $n$ bits of $X$ are the same as the first $n$ bits of $Y$ by toggling if necessary.
  3. If you have reached $Y$, terminate
  4. Double $X$ and go back to step 2.

The number of operations performed is apparently: $m-n$ to account for all doublings, plus the number of $1$'s in the lower $m-n$ bits of $Y$, plus possibly $1$ is the least significant of $X$ starts out wrong.

Hagen von Eitzen
  • 374,180
2

Note that we can "toggle" between the values $ 2n \leftrightarrow 2n+1 $ and otherwise the only operation is to double a value.

Let $X$ have the binary representation $a_0 a_1 \cdots a_{n-1} a_n$ and $Y$ have a binary representation $b_0 b_1 \cdots b_{n-1} b_n \cdots b_m $. $Y$ can only be reached from $X$ if $ a_i =b_i$ for $i=0, \cdots n-1$ and this can be achieved in $ n_0 + 2n_1 + \alpha $ steps. Where $n_0$ is the number of zeros in $b_{n+1} \cdots b_m $ , $n_1$ is the number of ones in $b_{n+1} \cdots b_m $ and $ \alpha $ is zero or one according to weather $a_n$ and $b_n$ are equal or unequal respectively.

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73