Traversing a binary tree to get from one number to another using only two operations

user_15493094 0
Viewed 74

I'm doing a problem that says that we have to get from one number, n, to another, m, in as few steps as possible, where each "step" can be 1) doubling, or 2) subtracting one. The natural approach is two construct a binary tree and run BFS since we are given that n, m are bounded by 0 ≤ n, m ≤ 104 and so the tree doesn't get that big. However, I ran into a stunningly short solution, and have no idea why it works. It basically goes from m … n instead, halving or adding one as necessary to decrease m until it is less than n, and then just adding to get up to n. Here is the code:

    while(n<m){
        if (m%2) m++;
        else m /= 2;
        count++;
    }

    count  = count  + n - m;
    return count;

Is it obvious why this is necessarily the shortest path? I get that going from m … n is natural because n is lower bounded by zero and so the tree becomes more "finite" in some sense, but this method of modified halving until you get below the number, then adding up until you reach it, doesn't seem like it should necessarily always return the correct answer, yet it does. Why, and how might I have recognized this approach from the get-go?

binary-tree breadth-first-search math algorithm c++
1 Answers

You only have 2 available operations:

  1. double n
  2. subtract 1 from n

That means the only way to go up is to double and the only way to go down is to subtract 1.

If m is an even number, then you can land on it by doubling n when 2*n = m. Otherwise, you will have to subtract 1 as well (if 2*n = m + 1 then you will have to double n and then subtract 1).

If doubling n lands too far above m then you will have to subtract twice as many times than if you used the subtraction before doubling n.

example: n = 12 and m = 20.
You can either double n and then subtract 4 times as in 12*2 -4 = 20. - 5 steps
Or you can subtract twice and then double n as in (12-2)*2 = 20. - 3 steps

You might be wondering 'How should I pick between doubling or subtracting when n < m/2?'.

The idea is to use a reccurence-based approach. You know that you want n to reach a value of v such as v = m/2 or v = (m+1)/2. In other words you want n to reach v... and the shortest way to do that is to reach a value v' such as v' = v/2 or v' = (v+1)/2 and so on.

example: n = 2 and m = 21.
You want n to reach (21+1)/2 = 11 which means you want to reach (11+1)/2 = 6 and thus to reach 6/2=3 and thus to reach (3+1)/2 = 2.
Since n=2 you now know that the shortest path is: (((n*2-1)*2)*2-1)*2-1.

other example: n = 14 and m = 22.
You want n to reach 22/2 = 11.
n is already above 11 so the shortest path is : (n-1-1-1)*2.

From here, you can see that the shortest path can be deduced without a binary tree. On top of that, you have to think starting from m and going down to an obvious path for n. This implies that it will be easier to code an algorithm going from m to n than the opposite.

Using recurrence, this function achieves the same result:

function shortest(n, m) {
    if (n >= m) return n-m; //only way to go down

    if(m%2==0) return 1 + shortest(n, m/2); //if m is even => optimum goal is m/2
    else       return 2 + shortest(n, (m+1)/2);//else optimum goal is (m+1)/2 which necessitates 2 operations
}
user_86630750
Related