Minimum number of operations to get from x to y given following operations

Question

What is the fastest way to get the minimum number of operations by converting x to y?

You can:

1. multiply x by 2
2. divide x by 2 (if even)
3. increment x

x can be greater than or less than y

Is there a greedy way to do this problem faster than brute force dfs?

Answer 1

You can do this in O(log^2 (max(x,y))) time, which is far better than breadth-first search which takes O(max(x,y)) time.

I'll assume that x and y are nonnegative. The key is to find sequences of operations that can't appear in an optimal transformation sequence.

Let P, M, D denote the (Plus_one, Multiply_by_2 and Divide_by_2) operations, respectively. Immediately, we know that MD and DM can't occur as a substring. We also know that MPP doesn't occur (since PM is shorter and equivalent).

Furthermore, after M appears once, D can never occur again. This is true because the first D after an M would have to be immediately preceded by either M or MP, which are both impossible. In fact, after M appears once in our sequence, PP can never occur again either, since it would have to come immediately after an M or a P.

Finally, PPD can't occur (since DP is shorter and equivalent), and in fact D can never appear after PP has appeared once: D can't appear anymore once M has appeared, so for D to appear after PP, it would have to appear immediately after as PPD, which we just showed to be impossible.

Putting these facts together, the optimal transformation sequence has the form:

(D OR PD)* + (P)* + (M OR MP)* where + is string concatenation and * is the Kleene star (i.e. take 0 or more copies). This is the most important part: everything follows from this expression.

As an informal summary: the optimal transformation sequence repeatedly removes the final digit of x (in binary) until it's 'small enough', then adds 1 until x is a prefix of y, then extends x to y by multiplying by 2 (and adding 1, if needed to match up with y).

Here's a typical example, showing the three "phases" of an optimal sequence:

Converting 5838 to 2523
1011011001110 -> 
 100111011011


// Shrinking phase begins: remove last digit using D or PD

1011011001110
101101100111
101101101000
10110110100
1011011010
101101101
101101110
10110111
10111000
1011100
101110
10111
11000
1100
110       // Shrinking has stopped: time to add ones
111
1000
1001      // Adding ones has stopped: we have a prefix of y to expand
10010
10011
100110
100111
1001110
10011100
10011101
100111010
100111011
1001110110
10011101100
10011101101
100111011010
100111011011

By the structure of the third term, (M OR MP)*, our transformed number from x before the occurrence of the first M must be a prefix of y. Furthermore, if u is a prefix of v (as binary strings), then you can easily show by induction that the shortest way to transform u to v uses only M and MP.

---

The algorithm

The algorithm is as follows: first, we need a function add_until_prefix(a, b) which finds the number of times to add one to a until it is a prefix (in binary) of b. This counts the (P)* term.

Then, we need a function to count the operations M and MP to extend a prefix of y, 'prefix', to y itself. That function is num_bits(y) + num_set_bits(y) - (num_bits(prefix) + num_set_bits(prefix)). This counts the (M OR MP)* term.

Finally, we need to figure out the number of times to repeat the first term (D OR PD)*. Fortunately, we can just try all of the possibilities, since there's only log(x) of them, and each can be checked in O(log x) time. To loop over possibilities, we do:

While x is greater than 0:

1. Try to add 1 to x until it is a prefix of y, and then extend this prefix to y. If the number of steps required is smaller than our previous best, take this number of steps as our current best.
2. Remove the last digit of x (with either D or PD), depending on whether x is even or odd, respectively.

---

Python implementation (which returns the path, too):

def min_ops_sequence(x: int, y: int) -> Tuple[Union[int, float], List[int]]:
    """Returns the minimum number of steps to get from x to y and the path.
    Allowed operations in a step: mult. x by 2, divide x by 2 if even, increment x.
    x and y must be nonnegative integers.
    """

    # Edge cases
    if x == y:
        return 0, []
    if x < 0 or y < 0:
        raise ValueError
    if y == 0 and x > 0:
        return math.inf, []

    # Upper bound; more than enough steps to reduce x to zero then build y in binary
    max_operations_allowed = 5 * (x.bit_length() + y.bit_length() + 1)

    def add_until_prefix(curr_num: int,
                         curr_path: List[int],
                         upper_limit=max_operations_allowed) -> bool:
        """Add one until prefix reached, unless we exceed some limit"""
        assert curr_num <= y

        y_copy = y
        # Find smallest prefix of y that is larger than curr_num
        while y_copy // 2 >= curr_num:
            y_copy //= 2

        best_diff = y_copy - curr_num
        if best_diff > upper_limit:
            return False
        while curr_num < y_copy:
            curr_num += 1
            curr_path.append(curr_num)
        return True

    def complete_prefix_of_y(prefix: int, curr_path: List[int]) -> None:
        """Given a prefix of y (in binary), append to path the numbers encountered
        while transforming the prefix to y by the operations 
        (t->2t, or (t-> 2t -> 2t+1))"""

        smaller = bin(prefix)
        larger = bin(y)
        remaining_digs = list(larger[len(smaller):])
        remaining_digs.reverse()
        while len(remaining_digs) > 0:

            prefix = 2 * prefix
            curr_path.append(prefix)

            if remaining_digs.pop() == '1':
                prefix += 1
                curr_path.append(prefix)
        return

    best_len, best_path = math.inf, []
    before_path = []

    # Repeatedly remove last digit of x (in binary) and test new distance to y
    while True:
        before_path.append(x)
        this_path = before_path[:]
        if x <= y:
            successful = add_until_prefix(x,
                                          this_path,
                                          min(max_operations_allowed,
                                              best_len-len(this_path)+2))
            if successful:
                complete_prefix_of_y(this_path[-1], this_path)
                if len(this_path) < best_len:
                    best_len = len(this_path)
                    best_path = this_path
        if x % 2 == 1:
            if x == 1:
                break
            before_path.append(x + 1)
            x += 1
        x //= 2

    return best_len - 1, best_path

Running:

print(min_ops_sequence(48, 64)[1])
print(min_ops_sequence(5, 18)[1])
print(min_ops_sequence(11, 28)[1])

gives:

[48, 24, 12, 13, 14, 15, 16, 32, 64]
[5, 6, 7, 8, 9, 18]
[11, 12, 13, 14, 28]