Suppose we are given two positive integers, a and b. Each move we are allowed to divide a by 2 (but only if a is even), multiply a by 2, or add 1 to a. How many moves does it take to change a to b? Find either a direct formula or an efficient algorithm (i.e. one that runs in logarithmic time).

Some progress that I have made: We can think of it as writing b=(2^k)a something, where this "something" can be expressed by the sum of powers of 2 (including negative exponents). Clearly we'd want to choose k so that k is a large as possible while maintaining (2^k)a<b, and we'd want k to be the total difference between the ×2s and the ÷2s. However I'm not too sure how to go from here. Does someone have solution?

CodePudding user response：

One approach I can think of is to maintain a tree, with the root node as the initial number. Every node has three children, each of which resembles one operation (double, half, increment), unless of course the number is odd, in which case the half operation won't be counted. You can do a simple BFS in order to find the first instance in which the target value is seen. Here is some sample code in C (p1 is the initial value, p2 is the target):

unordered_set<uint64_t> set; // Resembles the previous layer
unordered_set<uint64_t> visited; // Visited set. If we already came across a node, then there isn't any point in evaluating it again
set.insert(p1); // First layer contains the initial value
visited.insert(p1);
int count = 0;

while (!set.count(p2)) { // Loop until you reach the target value
    unordered_set<uint64_t> new_set; // Build the new layer

    for (uint64_t elem : set) {
        if ((elem & 1) == 0) { // Divide by two if it's even (>> 1 is the same as divide by 2)
            if (!visited.count(elem >> 1)) {
                new_set.insert(elem >> 1);
                visited.insert(elem >> 1);
            }
        }

        if (!visited.count(elem   1)) {
            new_set.insert(elem   1);
            visited.insert(elem   1);
        }
                
        if (!visited.count(elem << 1) && elem < p2) {
            new_set.insert(elem << 1);
            visited.insert(elem << 1);
        }
    }

    set = new_set; // Update current layer
    count  ;
}

cout << count << endl;

CodePudding user response：

Here's my take, done in C#.

var a = 2;
var b = 15;

var found = new HashSet<int>() { a };

int Remember(int value)
{
    found.Add(value);
    return value;
}

var operations = new[]
{
    new { operation = "/2", condition = (Func<int, bool>)(x => x % 2 == 0), projection = (Func<int, int>)(x => x / 2) },
    new { operation = "*2", condition = (Func<int, bool>)(x => x <= int.MaxValue / 2), projection = (Func<int, int>)(x => x * 2) },
    new { operation = " 1", condition = (Func<int, bool>)(x => true), projection = (Func<int, int>)(x => x   1) },
};

var candidates = new[] { new { count = 0, operations = $"{a}", value = a } };

while (!found.Contains(b))
{
    candidates =
    (
        from c in candidates
        from x in operations
        where x.condition(c.value)
        let test = x.projection(c.value)
        where !found.Contains(test)
        let value = Remember(test)
        select new
        {
            count = c.count  1,
            operations = $"{c.operations}, {x.operation}",
            value,
        }
    ).ToArray();
}

var result = candidates.Where(x => x.value == b).First();

Console.WriteLine($"{result.count} operations: {result.operations} = {result.value}");

That outputs:

5 operations: 2,  1, *2,  1, *2,  1 = 15

Basically, this is starting with a at the zeroth step. It then takes this generation and produces all possible values from the operations to create the next generation. If it produces a value that it has already seen it discards the value as there is an equal or faster operation to produce the value. It keeps repeating until b is found.