Finding least number of moves

Question

I have the following problem statement:

Given a number n (1 < n < 10^9), what is the least number of mathematical operations from the set (divide n by 2, divide n by 3, subtract 1 from n) that can be used to transform the number n to 1?

I have written the following code so far in an attempt to solve the problem:

while(n!=1){

    if(n%3==0 || n%2==0){
        if(n%3==0){
            n=n/3;
            c=c+1;
        }
        if(n%2==0){
        n=n/2;
        c=c+1;
        }
    }
    else{
        n=n-1;
        c=c+1;
    }
}
System.out.println(c);

But I dont get the desired output. Can someone help me with it.

Answer 1

I think that Tristan is right—you have no way to know which operation will end up yielding the shortest path up-front, so you have to try all of them in order to get the right answer.

Typically, a brute-force solution like this would imply that the calculation will take exponential time. You start with n, then calculate up to 3 new numbers using your 3 operations. Then for each of those 3 numbers you get another 3, totaling 9. Then for each of those 9 you get another 3, totaling 27; and so on. You can see how you would quickly end up with a ridiculous number of possibilities.

However, your search space here is limited. Since all of your operations will cause the value to decrease, you will only encounter numbers from 1 to n, inclusive. This means it will take at most n operations to reach your goal of 1. There's only one shortest-length path to each number, so once you've found that path you don't need to consider any other paths you find that lead to that same number. If you keep a set of previously seen numbers, you should be able to eliminate a huge portion of your search space since you can throw out repeated results. (This is a form of Memoization.)

Here's how I would do that problem:

1. Create a Set<Integer> to contain previously seen values.
2. Create a Map<Integer, Integer> to hold your active values. Each key → value entry's key would be a number in the path from n to 1, and the value would be the number of operations it took to reach that number.
3. Put the initial entry n → 0 in your active map.
4. While your active map does not contain a key with value 1 (your target):
   1. Create an empty map to hold your new active values.
   2. For each entry in active x → i :
      1. If x is divisible by 3 and x/3 is not in the seen set, then add x/3 to seen and put x/3 → i+1 into your new active map.
      2. Do something similar for x/2 and x-1.
   3. Replace your current active map with the new active map.
5. Return the value i for the entry 1 → i in your active map.

There are a few things you could do to speed this up a bit more (e.g. break out of the loop immediately when you find 1), or decrease the memory footprint (e.g. you discard sentries from the seen set if they're bigger than any of your active entries, or use a list instead of a map since all the i values for an iteration are the same), but this should be efficient enough to do what you need.

---

I've ported my solution to Java and posted it here:

http://ideone.com/qWt0LE

The output contains some timings. Note that the solution linked here uses a map for seen and a list for active. I store the previous number in the chain as the value for each map entry in seen, which allows me to reconstruct the chain at the end. In the output, 3 means divided by 3, 2 means divided by 2, and 1 means subtracted 1.