Multiply/add initial number to get target number

Question

Suppose I have a target number n e.g. 5, and I always start from the number 1 and I have to *2 or *3 or +1 to it until I reach n. So in this case I would *2 twice, then +1 to get 5.

I am supposed to find the least number of operations to reach the target value. I see a similar question being posted but that requires a fixed number of steps while I have to figure out the least steps. Are there any tips on how I can tackle this problem?

This is a homework problem.

Answer 1

It can be regarded as search or DP problem (yes in essence they are both related to state transition), the key point is to define search state condition, suppose n is positive, here we define f[i] = inf, inf is a really large integer means number i is not reachable, f[i] = k, k >= 0 means number i can be reached in at least k steps.

If n is not so large, we can use an array to store least steps for each number from 1 to n. The initial is that f[1] = 0 and f[i] = inf, 2 <= i <= n. If we need to output how we get the target(ex, output of 5 is 1 2 4 5), we can use another array pre to store the operations, define pre[i] = j means number i is produced by number j(ex, pre[4] = 2 means number 4 is produced by number 2, because 2*2=4; pre[3] = 1 means number 3 is produced by number 1, because 1*3=3):

    int inf = Integer.MAX_VALUE;
    f[1] = 0;
    pre[1] = -1; // pre[i] = -1 means i is the start point
    for(i=2;i<=n;i++) {
        f[i] = inf;
        pre[i] = -1;
    }

    for(int i=1;i<=n;i++) { // since each number is positive so smaller number cannot be produced via larger number, no need to consider > n issue
        if(f[i] == inf) {
            continue;
        }
        if(2*i <= n && f[i] + 1 < f[2*i]) {
            f[2*i] = f[i] + 1;
            pre[2*i] = i; // means number 2*i is produced by number i
        }
        if(3*i <= n && f[i] + 1 < f[3*i]) {
            f[3*i] = f[i] + 1;
            pre[3*i] = i;
        }
        if(i+1 <= n && f[i] + 1 < f[i+1]) {
            f[i+1] = f[i] + 1;
            pre[i+1] = i;
        }
    }

The answer is f[n].

How to output how we get target, we use the pre array to recover the operations:

        curr = n;
        pos = 0;
        ans[pos] = n;
        while(pre[curr] != -1) {
            pos++;
            ans[pos] = pre[curr];
            curr = pre[curr];
        }
        for(int i=pos;i>=0;i--) { // reverse order to output
            System.out.println(ans[i]);
        }

While if n is very large, you may need to use a priority queue to maintain state transition and a hash set to maintain least steps for each number.

Answer 2

I think the way to go here is to work backwards. Start from n and try the action that reduces it the most, then the second one in the list etc. The code could look something like this:

string actions = "";
int i = n, count = 0;

while (i > 1)
{
    count++;

    if (i % 3 == 0)
    {    
        i = i / 3;
        actions = "*3 " + actions;
        continue;
    }

    if (i % 2 == 0)
    {    
        i = i / 2;
        actions = "*2 " + actions;
        continue;
    }

    i--;
    actions = "+1 " + actions;
}

Essentially, the idea is to get to n as fast as possible. I am not sure this the least amount of steps, but it does seem like a good start.

Answer 3

Have you considered the AI approach?

Think of you problem as a search in a tree: the root is 1, and every node X in the tree has 3 sons: 2*X,3*X,X+1.

you can either build the whole tree (every node X where X>n shouldn't have more sons) and use BFS to find the shortest path from the root to a node that has the value n, or use A* algorithm in case the graph does not fit into memory.