7

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.

Community
  • 1
  • 1
maregor
  • 777
  • 9
  • 32

4 Answers4

8

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.

coderz
  • 4,847
  • 11
  • 47
  • 70
  • I'm not sure if this algorithm give best result or not, but this was nice in my opinion :) – Lrrr May 31 '15 at 09:21
  • This is the correct answer. I thought of it as a graph with edges between nodes that represent +1, *2 or *3, and the run a BFS with S=1 and T=n. +1 from me. – shapiro yaacov May 31 '15 at 09:30
  • @Lrrr The algorithm maybe not the best performance, but it can always get correct answer:) – coderz May 31 '15 at 09:41
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.

shapiro yaacov
  • 2,308
  • 2
  • 26
  • 39
  • 1
    Eg: Given n = 10 , Your way –> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ). But the optimal way is –> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ). – NIKUNJ KHOKHAR May 28 '18 at 12:54
1

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.

AvidLearner
  • 4,123
  • 5
  • 35
  • 48
0

This will give you the guaranteed shortest path.

static int result(int a, int b){
    int answer = 0;
    while (a < b){
        if (b % 3 == 0 && b / 3 >= a){
            b = b / 3;
            answer++;
        }
        else if ((b - 1) % 3 == 0 && (b - 1) / 3 >= a){
            b = b - 1;
            b = b / 3;
            answer += 2;
        }
        else if (b % 2 == 0 && b / 2 >= a){
            b = b / 2;
            answer++;
        }
        else{
            b = b - 1;
            answer++;
        }
    }

    return answer;
}
abshekv
  • 1
  • 1