Minimum Steps to One

问题:

Problem statement :

On a positive integer, you can perform any one of the following 3 steps.

1. Subtract 1 from it. ( n = n - 1 )
2. If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 )
3. If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ).

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1

eg:

1. For n = 1 , output: 0
2. For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 )
3. For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

I know the solution using dynamic programming and having a integer array. here is the code.

    public int bottomup(int n) {
            //here i am defining an integer array
            //Exception is thrown here, if the n values is high.
            public int[] bu = new int[n+1];
            bu[0] = 0;
            bu[1] = 0;
            for(int i=2;i<=n;i++) {
                    int r = 1+bu[i-1];
                    if(i%2 == 0) r = Math.min(r,1+bu[i/2]);
                    if(i%3 == 0) r = Math.min(r,1+bu[i/3]);
                    bu[i] = r;
            }
            return bu[n];
    }

But i want to solve this using less space.This solution throws OutofMemoryError in java if n=100000000.I don't want to increase my heap space.Does anyone has solution using less space?

Please note this problem cannot be solved using greedy algorthm.Using one while loop and check for divisible by 3 and divisible by 2 wont work.you have to use dynamic programming.please suggest if any has a solution using less space.

eg:

For n = 10 greedy algo is 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 which takes 4 steps.where as the solution should be 10-1 = 9 / 3 = 3 / 3 = 1, 3 steps.

I even tried topdown solution.

    public int[] td = null;
    public int topdown(int n) {
            if(n <= 1) return 0;
            int r = 1+topdown(n-1);
            if(td[n] == 0) {
                    if(n%2 == 0) r = Math.min(r,1+topdown(n/2));
                    if(n%3 == 0) r = Math.min(r,1+topdown(n/3));
                    td[n] = r;
            }
            return td[n];
    }

it is failing at n=10000.

回答1:

One idea is that at any iteration you need the values only for r/3 to r. So you can keep discarding 1/3rd of the array.

I'm not familiar with Java, but with C++ you can use a double ended queue (deque):

You keep adding to the deque from the back.
When i = 6, you do not need bu[0] and bu[1]. So you pop out two elements from the front of the queue.

Random access [ ] is supported with deque container.

EDIT: Also as suggested in the comments, you should change your datatype to a smaller sized one since the maximum number of steps shall be of the order of ( (log N) to base 2)

EDIT2: As Dukeling pointed out, it seems that in Java there is no ready-made well-suited implementation for deque that would not compromise on time complexity. You can think of implementing it in your own way as C++ does (I heard it is implemented as a vector of vectors with the size of inner vectors being small as compared to the total number of elements).

回答2:

UPDATE: Here is updated code which I have actually tested somewhat and I believe comes to the same answers for n from 1 to 100000. I'm leaving the original answer below for reference. The flaw was the "clever" use of MAX_INT. I forgot that there would be some cases where I skipped the -1 possibility but the number would also not be divisible by 2 or 3. This solves that by returning null to mean "this path is pointless to explore further".

public static int steps(int n) {
    return steps(n, 0);
}
private static Integer steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    Integer minSteps = null;
    if (consecutiveMinusOnes < 2) {
        Integer subOne = steps(n - 1, consecutiveMinusOnes + 1);
        if (subOne != null) {
            minSteps = 1 + subOne;
        }
    }
    if (n % 2 == 0) {
        Integer div2 = steps(n / 2, 0);
        if (div2 != null) {
            if (minSteps == null) {
                minSteps = div2 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div2);
            }
        }
    }
    if (n % 3 == 0) {
        Integer div3 = steps(n / 3, 0);
        if (div3 != null) {
            if (minSteps == null) {
                minSteps = div3 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div3);
            }
        }
    }
    return minSteps;
}

I believe this may work, but I haven't proved it. This algorithm is based on the idea that the only reason to subtract by one is to get you closer to a number divisible by 2 or 3. For this reason, you never really need to apply the subtract-by-one step more than two times consecutively, because if k % 3 == 2, then k - 2 % 3 == 0 and you can divide by three. Subtracting by one more times will be a wast of effort (you'll have also passed by at least one even number, so the best divide by two step opportunity will come up). This means a top down, recursive approach, and you can mix in some memoization if you want to:

public static int steps(n) {
    return steps(n, 0);
}
private static int steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    int minSteps = Integer.MAX_VALUE;
    if (consecutiveMinusOnes < 2) {
        minSteps = 1 + steps(n - 1, consecutiveMinusOnes + 1);
    }
    if (n % 2 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 2, 0));
    }
    if (n % 3 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 3, 0));
    }
    return minSteps;
}

DISCLAIMER: As I said above, I haven't proved this method works. I also haven't tested this particular implementation. I also haven't done the memoization stuff just because I'm lazy. Anyway, I hope that even if this doesn't quite work it gives you some ideas on how to modify your approach.

回答3:

This works :)

import java.util.Scanner;
public class MinimumStepToOne {

 public static void main(String[] args){
    Scanner sscan = new Scanner(System.in);
    System.out.print("Give a no:" + " ");

    int n = sscan.nextInt();
    int count = 0;
    for(int i = 0; n > 1; i++){

        if(n%2 == 0){n /= 2; count++;}
        else if(n%3 == 0){ n /= 3; count++;}
        else { n -= 1; count++;}

    }
    System.out.println("your no is minimized to: " + n);
    System.out.println("The min no of steps: " + count);    
 }
}