Min Steps to 1 using DP — Coding Question

Problem Statement:

Given a positive integer ’n’, find and return the minimum number of steps that ’n’ has to take to get reduced to 1. You can perform any one of the following 3 steps:

1.) Subtract 1 from it. (n = n — ­1) ,

2.) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,

3.) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).

Input format :

The first and the only line of input contains an integer value, ‘n’.

Output format :

Print the minimum number of steps.

Sample Input 1 :

4

Sample Output 1 :

2

Explanation of Sample Output 1 :

For n = 4
Step 1 :  n = 4 / 2  = 2
Step 2 : n = 2 / 2  =  1

Sample Input 2 :

7

Sample Output 2 :

3

Explanation of Sample Output 2 :

For n = 7
Step 1 :  n = 7 ­- 1 = 6
Step 2 : n = 6  / 3 = 2 
Step 3 : n = 2 / 2 = 1

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.