2
$\begingroup$

You are given an initial integer and a target integer. You may change the initial number by doing any of the operations $+2, -2, \times 2, \div 2$, any number of times in any order, to get the target number. For example, from $16$ to $40$, you may do $+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2$, or $\div 2, \div 2, +2, +2, +2, \times 2, \times 2$. The only restriction is that no intermediate operation may result on a fraction.

Is there a feasible algorithm (say, it takes $O(n \log n)$ time for a maximum absolute input of $n$) to find the shortest solution for a given pair of integers?

  • 1
    This is a shortest path problem in the graph with vertex set $V=\mathbb{N}$ and whose edges correspond to the allowed operations (i.e. 7 would be connected to 9, 5, and 14). You may be able to make an efficient algorithm out of this view by appropriately pruning the graph to have a finite (and small enough) number of vertices and then applying standard shortest path algorithms. At the moment I don't have time to think about the details.2012-09-20

1 Answers 1

2

Consider the following algorithm which takes $m$ to $0$:

  • Step 1: If $m=0$, exit.

  • Step 2: If $m$ is even, $m \mapsto m \div 2$.

  • Step 3: If $m$ is odd then

    • If $m>0$ then, $m \mapsto 2m \mapsto 2m-2 \mapsto (2m-2)/2=m-1$.

    • If $m<0$ then, $m \mapsto 2m \mapsto 2m+2 \mapsto (2m+2)/2=m+1$.

  • Step 4: Goto Step 1.

This algorithm terminates in $O(\log |m|)$ steps (a strict upper bound would be $4 \log_2 |m|$).

We can similarly apply the above algorithm on the input $n$ instead, which will take $n$ to $0$ in $O(\log |n|)$ steps. Importantly, we can reverse the steps, and hence take $0$ to $n$ in $O(\log |n|)$ steps.

Hence we can get from $m$ to $n$ in $O(\log |mn|)$ steps. This will be asymptotically the best possible (up to a constant factor).

(Comment: if e.g. $m$ is negative and $n$ is positive, then we must go through at least one of $\{-1,0,1\}$ since multiplication by $2$ and division by $2$ does not affect sign.)