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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

CS371p Spring 2022: David Klingler

Open Container Initiative (OCI) Specifications

TidyCoding++

Easily deploy Trino on Dataproc with init action script

Git Essential for productivity

How PMs + Agile Dev Teams Can See Eye-to-Eye: Follow up Questions

ProductStack Event Image.jpg

Week 1 — Reflecting on my Senior Thesis Project

Debug Your Laravel Project From Front to Back With Telescope

In this post, you’ll learn how you can use Laravel Telescope to monitor and debug your Laravel project. It turns 500 internal server errors into stacktraces that help you with debugging.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Condition required to detect queue full and queue empty-quiz question asked in interviews

[LeetCode] (Easy) 27. Remove Element

Dan Bunting — Game Developer

Leetcode — 1891. Cutting Ribbons