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

The simplest solution might be to explore all possibilities.

public static ArrayList<Integer> solve(int n, 
  ArrayList<Integer> moves, int bestMove,HashMap<Integer,Integer> memory) {

        if (moves.size() >= bestMove) return null;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves.size())return null;
        memory.put(n,moves.size());

        int size_1=Integer.MAX_VALUE, size_2 = Integer.MAX_VALUE, size_3 = Integer.MAX_VALUE;
        ArrayList<Integer> moves3 = null, moves2 = null, moves1;

        if (n % 3 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(3);
            moves3 = solve(n / 3, c,bestMove,memory);
            if (moves3!=null)
            size_3 = moves3.size();
        }

        bestMove = Math.min(bestMove, size_3);

        if (n % 2 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(2);
            moves2 = solve(n / 2, c,bestMove,memory);
            if (moves2!=null)
            size_2 = moves2.size();
        }

        bestMove = Math.min(bestMove, size_2);


        ArrayList<Integer> c = new ArrayList<Integer>(moves);
        c.add(1);
        moves1 = solve(n - 1, c,bestMove,memory);
        if (moves1!=null)
        size_1 = moves1.size();

        int r = Math.min(Math.min(size_1, size_2),size_3);
        if (r==size_1) return moves1;
        if (r==size_2) return moves2;

        return moves3;

    }

Explanation:

n : n

moves : An ArrayList containing the movements. (for printing pourposes)

bestMove : value containing size of the minimal solution found.

memory : a HashMap containing the "state" explored previously and the length of the path.

If we call public static void main(String[] args) {

    long a = System.currentTimeMillis();
    Object[] sol=solve(10, new ArrayList<Integer>(),Integer.MAX_VALUE,new HashMap<Integer,Integer>()).toArray();
    System.out.println(sol.length);
    System.out.println(Arrays.toString(sol));
    System.out.println((System.currentTimeMillis()-a));
}

The output would be:

3
[1, 3, 3]
1

Equivalent to n-1, n/3,n/3 (@Tristan's best solution)

if we call it with 1000 000 000 as n:

30
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
55

If we call it with 11:

4
[1, 1, 3, 3]
1

EDIT: If only the number of moves it's needed:

public static int solve(int n,int moves,int bestMove,HashMap<Integer,Integer> memory) {

        if (moves >= bestMove) return Integer.MAX_VALUE;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves)return Integer.MAX_VALUE;
        memory.put(n,moves);

        int size_1=Integer.MAX_VALUE;
        int size_2 = Integer.MAX_VALUE;
        int size_3 = Integer.MAX_VALUE;

        moves=moves+1;
        if (n % 3 == 0) size_3 = solve(n / 3, moves,bestMove,memory);
        bestMove = Math.min(bestMove, size_3);      
        if (n % 2 == 0) size_2=solve(n >> 1, moves,bestMove,memory);

        bestMove = Math.min(bestMove, size_2);

        size_1 = solve(n - 1, moves,bestMove,memory);


        return  Math.min(Math.min(size_1, size_2),size_3);


    }

Calling this method with

long a = System.currentTimeMillis();
System.out.println(
     solve(1000 *1000*1000, 0,Integer.MAX_VALUE,new HashMap<Integer,Integer>()));

    System.out.println((System.currentTimeMillis()-a));

Output:

30
24

Fast enough

Answer 2

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.

Answer 3

I believe question here is to just count the minimum number of steps, not the detail about steps, how to process it etc. So in that case below solution should be efficient and simplest one. Bottom up approach in Dynamic programming .

  int getMinOperations(int n) {
    // Use this array to store the previous solved result.
    int dp[] = new int[n + 1];
    // base case, if it is 1, we do not need to do any processing
    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
        // for the time being, let's assume we are getting minimum number of step by subtracting 1
        dp[i] = 1 + dp[i - 1];
        // if number if divisible by 2 let's divide it and compare it with the number of steps 
        // calculated in previous step, choose the minimum one
        if (i % 2 == 0)
            dp[i] = Math.min(dp[i], 1 + dp[i / 2]);
        // if number if divisible by 3 let's divide it and compare it with the number of steps 
        // calculated in previous step, choose the minimum one
        if (i % 3 == 0)
            dp[i] = Math.min(dp[i], 1 + dp[i / 3]);
        // At this step we have stored the minimum step to reduce the i to 1. and we will continue till nth value
    }
       // Returning nth value of array, as value at each index is the minimum number of steps to reduce it to 1.
    return dp[n];
}

Answer 4

Here is an interesting case to think about. From 10 you have a couple options:

10 / 2  = 5     1 move
5 - 1   = 4     2 moves
4 / 2   = 2     3 moves
2 - 1   = 1     4 moves


10 - 1  = 9     1 move
9 / 3   = 3     2 moves
3 / 3   = 1     3 moves

How about from a number that is two away from being divisible by 3? Starting from 11 we have these options:

11 - 1  = 10    1 move
10 / 2  = 5     2 moves
5 - 1   = 4     3 moves
4 / 2   = 2     4 moves
2 / 2   = 1     5 moves


11 - 1  = 10    1 move
10 - 1  = 9     2 moves
9 / 3   = 3     3 moves
3 / 3   = 1     4 moves

Maybe this only works if the number you are subtracting to get to is ALSO divisible by 3? Who knows, goodluck OP.

Answer 5

NOTE : this is NOT actual code , you need to think about corner cases , this is a pseudocode , which give logic about the algorithm .

This can be done recursively , but since n is very high , you need to memorize using extra space .

    fun(int n)
   {
        if(n==0) return INFINITY;
        if(n==1) return 0;  

        if(n%3==0)
        a = fun(n/3)

        if(n%2==0)
        b = fun(n/2)

        return min(fun(n-1) , a+1 , b+1)
}

Answer 6

Python implementations of two solutions using Dynamic Programming

1) Top-Down

def calculate(mins, n):
    if n<= 0:
        raise ValueError("input is not positive")
    if n == 1:
        return 0
    if (mins[n] != -1):
        return mins[n]

    result = 1 + calculate(mins, n-1)
    if (n % 2 == 0):
        result = min(result, 1 + calculate(mins, n // 2))  
    if (n % 3 == 0):
        result = min(result, 1 + calculate(mins, n // 3))

    mins[n] = result
    return result

def get_min_step_memoization (n):
    mins = [-1] * (n+1)
    return calculate(mins, n)

2) Bottom Up

def get_min_step_dp(n):
    if n<= 0:
        raise ValueError("input is not positive")
    results = [-1] * (n+1)
    results[1] = 0 

    for idx in range(2, n+1):
        results[idx] = 1 + results[idx-1]
        if (idx % 2 == 0):
            results[idx] = min(results[idx], 1 + results[idx//2])
        if (idx %3 == 0):
            results[idx] = min(results[idx], 1 + results[idx//3])

    return results[n]

Answer 7

Use memoization for speed.

Initialize your map:

n_to_steps = {1=>0, 2=>1, 3=>1}

Now calculate. Do not calculate everything from 1 to n... instead:

def f(n)
  if n isn't a key in our map
    n_to_steps[n] = min(1 + n%2 + f(n/2), 1 + n%3 + f(n/3))
  end
  return n_to_steps[n]
end

Answer 8

I think n= 10^9 points towards some logic , not just trying all possible cases and all permutations.
Here is what i got :

1 -> 0  
2 -> 1  
3 -> 1  
4 -> 2  
5 -> 3  
6 -> 2  
7 -> 3  
8 -> 3  
9 -> 2  
10 ->3  
11 ->4  
12 ->3  
13 ->4  
14 ->4  
15 ->3  
16 ->4  
17 ->5  
18 ->3  
19 ->4  
20 ->4  
21 ->4  

So i think fornula is :

    while(n!=1)
    {
     if(n%3==0)
       ans += 1  and  n/=3 
      else if (n%2==0)
       ans += 1  and  n/=2
      else n--  , ans+=1
    }  

GIVES ANSWER FOR N = 1000000000 in 0.06 seconds . http://ideone.com/0pfKoz

// PREVIOUS INCORRECT LOGIC : (fails for n=30 easily as pointed by @Dukeling)

while(n!=1)
{
 if(n%2==0 && n%3==0)
   ans += p1 + p2   and  n=1  {where n = 2^p1 * 3^p2 }
  else if (n%2!=0 && n%3 !=0)
   n--
  else if (n%2==0 && n%3 !=0)
   ans+=1  and n/=2 
  else if (n%2!=0 && n%3 ==0)
   ans+=1  and n/=3 
}   

Please clarify if you have got the answer to this question , and try to see if my logic works .