Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You can use $\TeX$ on this site by enclosing formulas in dollar signs; single dollar signs for inline formulas and double dollar signs for displayed equations. You can see the source code for any math formatting you see on this site by right-clicking on it and selecting "Show Math As:TeX Commands". Here's a basic tutorial and quick reference. There's an "edit" link under the question –  joriki Sep 20 '12 at 10:30
    
One possible way is As follows: Think of a number as a binary sequence. According to the last digit, either div2 or times2, -2, div2 behaves as a binary right-shifting operation (which is usually denoted as >>). Thus we can shift the original input repeatedly to clear the input. Now similar trick allows us to mimic the left-shifting operator (<<) and increment operator(++), which allow us to 'build up' the target number. This is the farthest from what we regard as natural, but anyway it proves that we can find such a one. –  sos440 Sep 20 '12 at 10:35
1  
Finding the optimal result seems hard. The naive algorithm I imagine, prompted by sos440, would go from 12 to 21 by 12,6,3,1,2,4,8,10,20,40,42,21, but you can also do 12,6,4,8 and so on. –  Ross Millikan Sep 20 '12 at 13:27
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. –  Noah Stein Sep 20 '12 at 13:47
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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