Minimum number of operations to get from source to target.

Question

I came across this question during an interview - Convert a number source to target in the minimum number of operations.

Allowed Operations

1. Multiplied by 2.
2. Addition by 1.
3. subtraction by 1.

0 < source, target <= 1000.

I tried going the naive recursive route(O(3^n)) ie. subtract 1, add 1 and multiply by 2 at each level to try and find a solution that I could extend to Dynamic Programming but couldnt because of an infinite loop.

//Naive approach Via Recursion 

int minMoves(int source, int target){

    if(source <1 || source > target){
        return -1;
    }

    int moves =0;
    // Potential infinite loop - consider 3,6-> 2,6- >1,6->(0,6)x (2,6)->1,6->(0,6)x (1,6)->(0,6)x (2,6)->1,6..
    int movesLeft  = minMoves(source -1, target) ==-1? Integer.MAX_VALUE:minMoves(source -1, target);
    int movesRight  = minMoves(source +1, target) ==-1? Integer.MAX_VALUE:minMoves(source +1, target);
    int moves2X  = minMoves(2*source, target) ==-1? Integer.MAX_VALUE:minMoves(2*source, target);

    moves = 1+ Math.min(Math.min(movesRight,movesLeft), moves2X);
    return moves;

}

Any ideas on how I can tweak my solution? Or possibly a better way to solve it?

Answer 1

If you think about your solution like a graph traversal, where each node is an intermediate value you can produce, your recursive solution is like a depth first search (DFS). You'll have to fully expand until you've tried all solutions from that "branch" of the search space before you can proceed anywhere else. If you have an infinite loop, this means it will never terminate even if a shorter path exists, and even if you don't have an infinite loop, you still have to search the rest of the solution space to make sure its optimal.

Instead, consider an approach similar to breadth first search (BFS). You expand outward uniformly, and will never search a path longer than the optimal solution. Just use FIFO queue to schedule which node to access next. This is the approach I've taken with my solver.

from queue import Queue

def solve(source, target):
    queue = Queue()
    path = [source]
    queue.put(path)
    while source != target:
        queue.put(path + [source * 2])
        queue.put(path + [source + 1])
        queue.put(path + [source - 1])

        path = queue.get()
        source = path[-1]
    return path

if __name__ == "__main__":
    print(solve(4,79))