Minimum Steps to One

user_2602627 0
Viewed 8612

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.

dynamic-programming math algorithm java
5 Answers

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];

    }
user_134593130

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

user_154134820
Related