Home » Interview coding problems/challenges

# Minimum steps to minimize n as per given condition

**Minimum steps to minimize n as per given condition**: Here, we are going to see how to solve a recursion problem efficiently by memorization.

Submitted by Radib Kar, on June 13, 2020

**Problem statement:**

Given a number * n*, count minimum steps to minimize it to 1 performing the following operations:

- Operation1: If
is divisible by 2 then we may reduce n to**n**.**n/2** - Operation2: If
is divisible by 3 then you may reduce n to**n**.**n/3** - Operation3: Decrement n by 1.

**Input:**

Input is a single integer, * n*.

**Output:**

Output the **minimum number of steps to minimize the number** performing only the above operations.

**Constraints:**

1 <= N <= 10000

**Example:**

Test case 1: Input: N=10 Output: Minimum number of steps needed: 3 Test case 2: Input: N=6 Output: Minimum number of steps needed: 2

**Explanation:**

For the above test case, N=10 N is not divisible by 3, but by 2 So, 10->5 Now % is again neither divisible by 3 nor 2 So, only option is to decrement Hence 5->4 4 can be decremented to 2 by dividing by 2 4->2 2->1 So, The conversion path will be 10->5->4->2->1 Total 4 steps But is this the optimal one? Answer is no The optimal will be 10 converted to 9 by decrementing 10->9 9->3->1 So, total of 3 steps which is the minimum number Hence answer would be 3

**Solution Approach:**

The above problem is a classic recursion example.

Like,

- If
is divided by both 2 and 3**n**

Recur for possibilities*(n/3), (n/2), (n-1)* - If
is divided by only 3 but not by 2 then**n**

Recur for possibilities*(n/3), (n-1)* - If
is divided by only 2 but not by 3 then*n*

Recur for possibilities*(n/2), (n-1)* - If
is divided by only 3 but not by 2 then**n**

Recur for possibilities*(n/3), (n-1)* - If
is not divisible by both 2 and 3**n**

Then only recur for*(n-1)*

We can write all this with help of recursive function,

Let, f(n) = the minimum number of steps to convert n to 1

If you draw the recursion tree for * f(10)* you will find many overlapping sub-problems. Hence, we need to store all the already computed sub-problems through memorization.

Function minimumSteps(n) if(n==1) return 0; // memoization here, no need to compute if already computed if(dp[n]!=-1) return dp[n]; // store if not computed if(n%3==0 && n%2==0) dp[n]=1+min(minimumSteps(n-1),min(minimumSteps(n/3),minimumSteps(n/2))); else if(n%3==0) dp[n]=1+min(minimumSteps(n-1),minimumSteps(n/3)); else if(n%2==0) dp[n]=1+min(minimumSteps(n-1),minimumSteps(n/2)); else dp[n]=1+minimumSteps(n-1); end if return dp[n] End Function

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int dp[10001]; int minimumSteps(int n) { if (n == 1) return 0; if (dp[n] != -1) return dp[n]; if (n % 3 == 0 && n % 2 == 0) { dp[n] = 1 + min(minimumSteps(n - 1), min(minimumSteps(n / 3), minimumSteps(n / 2))); } else if (n % 3 == 0) { dp[n] = 1 + min(minimumSteps(n - 1), minimumSteps(n / 3)); } else if (n % 2 == 0) { dp[n] = 1 + min(minimumSteps(n - 1), minimumSteps(n / 2)); } else dp[n] = 1 + minimumSteps(n - 1); return dp[n]; } int main() { int n, item; cout << "enter the initial number, n \n"; cin >> n; for (int i = 0; i <= n; i++) dp[i] = -1; cout << "Minimum number of steps: " << minimumSteps(n) << endl; return 0; }

**Output:**

RUN 1: enter the initial number, n 15 Minimum number of steps: 4 RUN 2: enter the initial number, n 7 Minimum number of steps: 3

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.