Dynamic Programming - Minimum steps to 1

1 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement

Given a positive integer - num, Following is a list of possible operations which can be performed on it:
1. num / 2, If number is divisible by 2
2. num / 3, If number is divisible by 3
3. num - 1

With these 3 available operations, find out the minimum number of steps required to reduce the number to 1.

For example:
1. For num = 1, no. of steps needed - 0
2. For num = 2, no. of steps needed - 1 (num/2)
3. For num = 6, no. of steps needed - 2 (num/3 followed by num/2)
4. For num = 9, no. of steps needed - 2 (num/3 followed by num/3)

Building the solution

The very first thought that comes to mind after looking at the examples above is to try with num/3 if it divisible by 3, if not then try with num/2 if divisible by 2. If none of them works, the only option left is to do num - 1. This approach - commonly known as Greedy Approach - seems to work for all the above examples. But, How about 10 ?

Step 1: 10/2 => 5, since 10 is divisible by 2.
Step 2: 5 - 1 => 4, since 5 is neither divisible by 2 nor 3, so only option is to decrement the number.
Step 3: 4/2 => 2
Step 4: 2/2 => 1

So, it requires 4 steps to reduce the number 10 to 1. But, the question is - is that the best we can do ? How about the following alternative solution;

Step 1: 10 - 1 => 9
Step 2: 9/3 => 3
Step 3: 3/3 => 1

Clearly, this one beats the solution that we discussed earlier. The learning from this later solution is that in order to find the minimum number of steps, it is required to evaluate all possible operation at each and every step and then pick up that operation which results in least number of overall steps. Yes, it sounds confusing. May be this would help:

Consider num to be 10 and F(10) be the solution. Now, there are two possible operations that we can perform here - num -1 and num/2. To get the overall minimum we need to evaluate these two sub-problems one by one and then decide which one of them will lead us to optimal solution. In other words, we need to first evaluate F(9) (num - 1) and F(5) (num/2).
F(9) = 2
F(5) = 3
Based on this, we will choose F(9) to be part of our overall solution which we are interested in. In general, we can have something like this:

F(num) = 1 + MIN(F(n-1), F(n/2), F(n/3));
Sounds Familiar ?? Yes, Recursion is the way to go...

Recursive solution

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b,c) ((a) < (b)) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c))

int min_steps(int num);
int main(void) {
int num;

printf("Enter the number: ");
scanf("%d", &num);

printf("The minimum number of steps to go down to 1 is: %d\n", min_steps(num));
return 0;
}

int min_steps(int num)
{
int x = num, y = num, z = num;

if (num <= 1) return 0;

if (num%2 == 0) {
x = min_steps(num/2);
}

if (num%3 == 0) {
y = min_steps(num/3);
}

z = min_steps(num-1);

return 1+ (MIN(x,y,z));
}


Dynamic Programming solution

Above recursive solution does the right thing and is the most natural way to solve this problem. But do you see the problem? As it happens with most of the recursive solutions, the same subproblem is being solved multiple number of times. See the image below:

Dynamic Programming - Minimum steps to 1 | EduSagar



Although, the image is not complete in the sense that not all paths are reaching the terminal state, Still you get the idea. For example, F(2) will be evaluated while we try to solve F(3), F(4), F(5), F(6), F(7), F(8) and F(9). If you remember basic rules for Dynamic Programming, this problem perfectly fits in there. It has a recurrence relation with overlapping subproblems. To solve it using Dynamic Programming, we need to have extra space and we need to iterate over all possible operations as before. But, the good part is - we will solve one subproblem only once and store away the result in an array which will be referenced later.

For example, once we have solved F(2), we can store it in arr[2]. Now, when we try to solve F(2) as part of subproblems - F(3), F(4), F(5) etc. we can directly use the value of arr[2].

By definition - arr[i] will always store the minimum number of steps to reduce integer 'i' to 1 and hence is the optimal solution for 'i'.

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b) ((a) < (b)) ? (a) : (b)
#define NO_OP 0
#define SUB_1 1
#define DIV_2 2
#define DIV_3 3

int main(void) {
        int num=10;
        int i;
        int *out;
        int *res;

        printf("Enter the number: ");
        scanf("%d", &num);

        out = (int*)malloc(sizeof(int) * (num+1));
        res = (int*)malloc(sizeof(int) * (num+1));

        out[1] = 0;
        res[1] = NO_OP;
        for(i=2; i <= num; i++) {
                out[i] = out[i-1] + 1;
                res[i] = SUB_1;
               
                if (i%2 == 0) {
                    if ((out[i/2] + 1) < out[i]) {
                        res[i] = DIV_2;
                    }
                    out[i] = MIN(1 + out[i/2], out[i]);
                }
                if (i%3 == 0) {
                    if ((out[i/3] + 1) < out[i]) {
                        res[i] = DIV_3;
                    }
                    out[i] = MIN(1 + out[i/3], out[i]);
                }
        }

        printf("The minimum number of steps to go down to 1 is: %d\n", out[num]);
       
        // Print the sequence, we already know the number of steps to print
        for (i = out[num]; i > 0; i--) {
            printf("%d,", res[num]);
           
            if (res[num] == SUB_1) {
                num = num - 1;
            } else if (res[num] == DIV_2) {
                num = num / 2;
            } else {
                num = num / 3;
            }
        }
        printf("\n");
       
        return 0;
}


That was simple, and so is Dynamic Programming. Have Fun !!

comments powered by Disqus