Minimum Steps to One

Question

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.

Answer 1

This is a c++ recursive Solution for the above question

// Recursive Approach

    int minSteps(int n)
    {
        if (n == 1)
        {
            return 0;
        }
        int x, y = INT_MAX, z = INT_MAX;
        // Brute Force Approach
        x = minSteps(n - 1);
        if (n % 2 == 0)
        {
            y = minSteps(n / 2);
        }
        if (n % 3 == 0)
        {
            z = minSteps(n / 3);
        }
        return 1 + min(x, min(y, z));
    }

This is the memoization technique :

// memoization it could looks like difficult but trust me if you get to know how recursion is working memoization is the best way to improve your complexity drasticaly

    int memoMiniSteps(int n)
    {   
        int * arr = new int[n];
        for(int i = 0 ;i<n ;i++){
            arr[i]=-1;
        }
        if (n == 1)
        {
            return 0;
        }
        int x, y = INT_MAX, z = INT_MAX;
        // Memoization Approach
        if(arr[n-1]!=-1){
            x = arr[n-1];
        }else{
            x = minSteps(n - 1);
            arr[n-1]=x;
        }
    
        if (n % 2 == 0)
        {   
            if(arr[n/2]!=-1){
                y=arr[n/2];
            }else{
                y = minSteps(n / 2);
                arr[n/2]=y;
            }
        }
        if (n % 3 == 0)
        {
            if(arr[n/3]!=-1){
                y=arr[n/3];
            }else{
                y = minSteps(n / 3);
                arr[n/3]=y;
            }
        }
        arr[n]= 1 + min(x, min(y, z));
        return arr[n];
    }

// Now at last Dynamic Programming Approach It's best out of those 2 codes and simple to understand I still recommend this please try to understand the logic behind recursion first because Dp is all about optimizing the problems nothing else

DP approach

    int DpMinCount(int n){
        int *a = new int[n+1];
        a[0]=0;
        a[1]=0;
        for(int i =2 ; i<n+1 ;i++){
            int ans = a[i-1]+1;
            if(i%2==0){
                ans = min(ans,a[i/2]+1);
            }
            if(i%3==0){
                ans = min(ans,a[i/3]+1);
            }
        a[i]=ans;
        }
        return a[n];

}

Pictorial Representation :

enter image description here

Answer 2

Recursive Solution For this problem

public static int countMinStepsTo1(int n){

      if(n==1)
      {
          return 0;
      } 
      int count1,count2=Integer.MAX_VALUE,count3=Integer.MAX_VALUE;

      count1 = countMinStepsTo1(n-1);

       if((n%2)==0)
       {
           count2=countMinStepsTo1(n/2);
       }
        if((n%3)==0)
        {
            count3=countMinStepsTo1(n/3);
        }

        return 1+Math.min(count1,Math.min(count2,count3));
    }

DP Approch For this problem

public static int countstepsDP(int n)
    {
        int storage[] = new int[n+1];
        storage[1]=0;

        for(int i=2; i<=n;i++)
        {
            int min=storage[i-1];
            if(i%3==0)
            {
                if(min>storage[i/3])
                {
                    min=storage[i/3];
                }
            }
            if(i%2==0)
            {
                if(min>storage[i/2])
                {
                    min=storage[i/2];
                }
            }
            storage[i]=1+min;
        }

        return storage[n];

    } 

Answer 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);    
 }
}

Answer 4

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).

Answer 5

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.