Generate any number in the fewest step using multiply by 2 or divide by 3?

Question

Generate any number in the fewest step using multiply by 2 or divide by 3? Any idea how to solve this problem efficiently? I am thinking about dynamic programming but not sure. So for example, the best solution I can think of to get 7 is through 2*2*2*2*2*2/3/3 = 7. I mean integer division in C++ or Java here. Thanks!

Answer 1

Here is a BFS dynamic programming solution.

#! /usr/bin/env python
wanted = 7
found = {1: None}
added = [1]
while True:
    new_added = []
    for x in added:
        if 2*x not in found:
            found[2*x] = [x, 2]
            new_added.append(2*x)
        if x/3 not in found:
            found[x/3] = [x, 3]
            new_added.append(x/3)
    if wanted in found:
        break
    # This magic line copies new_added over the added array.
    added[:] = new_added

answer = []
path = [wanted]
while path[-1] != 1:
    node = found[path[-1]]
    path.append(node[0])
    answer.append(node[1])

print([x for x in reversed(answer)])
print([x for x in reversed(path)])

Here is an explanation.

BFS means Breadth-First Search. In this case we are searching in parallel through all paths of lengths 1, 2, 3, etc until we are done.

Dynamic Programming refers to any of a variety of methods to store a record of work done so that we can either avoid work, or refer back to already done work.

In this case found is a record of all numbers that we have found a path to with the integer you get there from, and what operation to use. added is the record of all integers that we found on the last pass. new_added is all of the integers that we found on this pass.

So we start with a record saying that we know how to get to 1. Then in each pass we take all of the just added records and see what new ones we get to by multiplying by 2 or dividing by 3.

We stop once we found our target. And then it is a question of finding the path back through found to get back to 1. This gives us our answer but in reverse order - the end of the path is at the start of our list. So reverse it and we have our answer.

Which I displayed both as a record of all of the numbers we visit and as a record of the operations.