Give an integer N, the task is to find the minimum number of moves to reduce N to 0 by one of the following operations:
- Reduce N by 1.
- Reduce N to (N/2), if N is divisible by 2.
- Reduce N to (N/3), if N is divisible by 3.
Examples:
Input: N = 10
Output: 4
Explanation:
Here N = 10
Step 1: Reducing N by 1 i.e., 10 – 1 = 9.
Step 2: Since 9 is divisible by 3, reduce it to N/3 = 9/3 = 3
Step 3: Since again 3 is divisible by 3 again repeating step 2, i.e., 3/3 = 1.
Step 4: 1 can be reduced by the step 1, i.e., 1-1 = 0
Hence, 4 steps are needed to reduce N to 0.Input: N = 6
Output: 3
Explanation:
Here N = 6
Step 1: Since 6 is divisible by 2, then 6/2 =3
Step 2: since 3 is divisible by 3, then 3/3 = 1.
Step 3: Reduce N to N-1 by 1, 1-1 = 0.
Hence, 3 steps are needed to reduce N to 0.
Naive Approach: The idea is to use recursion for all the possible moves. Below are the steps:
- Observe that base case for the problem, if N < 2 then for all the cases the answer will be N itself.
- At every value of N, choose between 2 possible cases:
- Reduce n till n % 2 == 0 and then update n /= 2 with count = 1 + n%2 + f(n/2)
- Reduce n till n % 3 == 0 and then update n /= 3 with count = 1 + n%3 + f(n/3)
- Both the computation results in the recurrence relation as:
count = 1 + min(n%2 + f(n/2), n%3 + f(n/3))
where, f(n) is the minimum of moves to reduce N to 0.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// number to steps to reduce N to 0int minDays(int n){ // Base case if (n < 1) return n; // Recursive call to count the // minimum steps needed int cnt = 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3)); // Return the answer return cnt;}// Driver Codeint main(){ // Given number N int N = 6; // Function call cout << minDays(N); return 0;}// This code is contributed by 29AjayKumar |
Java
// Java program for the above approachclass GFG{ // Function to find the minimum // number to steps to reduce N to 0 static int minDays(int n) { // Base case if (n < 1) return n; // Recursive Call to count the // minimum steps needed int cnt = 1 + Math.min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3)); // Return the answer return cnt; } // Driver Code public static void main(String[] args) { // Given Number N int N = 6; // Function Call System.out.print(minDays(N)); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the above approach# Function to find the minimum# number to steps to reduce N to 0def minDays(n): # Base case if n < 1: return n # Recursive Call to count the # minimum steps needed cnt = 1 + min(n % 2 + minDays(n // 2), n % 3 + minDays(n // 3)) # Return the answer return cnt# Driver Code# Given Number NN = 6# Function Callprint(str(minDays(N))) |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum// number to steps to reduce N to 0static int minDays(int n){ // Base case if (n < 1) return n; // Recursive call to count the // minimum steps needed int cnt = 1 + Math.Min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3)); // Return the answer return cnt;}// Driver Codepublic static void Main(String[] args) { // Given number N int N = 6; // Function call Console.Write(minDays(N));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum// number to steps to reduce N to 0function minDays(n){ // Base case if (n < 1) return n; // Recursive call to count the // minimum steps needed var cnt = 1 + Math.min(n % 2 + minDays(parseInt(n / 2)), n % 3 + minDays(parseInt(n / 3))); // Return the answer return cnt;}// Driver Code// Given number Nvar N = 6;// Function calldocument.write( minDays(N));</script> |
Output
4
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use Dynamic Programming. The above recursive approach results in TLE because of the number of repeated subproblems. To optimize the above method using a dictionary to keep track of values whose recursive call is already performed to reduce the further computation such that value can be accessed faster.
Below is the implementation of the above approach:
C++
// C++ program for // the above approach#include<bits/stdc++.h>using namespace std;// Function to find the minimum// number to steps to reduce N to 0int count(int n){ // Dictionary for storing // the precomputed sum map<int, int> dp; // Bases Cases dp[0] = 0; dp[1] = 1; // Check if n is not in dp then // only call the function so as // to reduce no of recursive calls if ((dp.find(n) == dp.end())) dp[n] = 1 + min(n % 2 + count(n / 2), n % 3 + count(n / 3)); // Return the answer return dp[n];}// Driver Codeint main(){ // Given number N int N = 6; // Function call cout << count(N);}// This code is contributed by gauravrajput1 |
Java
// Java program for the above approachimport java.util.HashMap;class GFG{ // Function to find the minimum// number to steps to reduce N to 0static int count(int n){ // Dictionary for storing // the precomputed sum HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>(); // Bases Cases dp.put(0, 0); dp.put(1, 1); // Check if n is not in dp then // only call the function so as // to reduce no of recursive calls if (!dp.containsKey(n)) dp.put(n, 1 + Math.min(n % 2 + count(n / 2), n % 3 + count(n / 3))); // Return the answer return dp.get(n);}// Driver Codepublic static void main(String[] args){ // Given number N int N = 6; // Function call System.out.println(String.valueOf((count(N))));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to find the minimum# number to steps to reduce N to 0def count(n): # Dictionary for storing # the precomputed sum dp = dict() # Bases Cases dp[0] = 0 dp[1] = 1 # Check if n is not in dp then # only call the function so as # to reduce no of recursive calls if n not in dp: dp[n] = 1 + min(n % 2 + count(n//2), n % 3 + count(n//3)) # Return the answer return dp[n]# Driver Code# Given Number NN = 6# Function Callprint(str(count(N))) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the minimum// number to steps to reduce N to 0static int count(int n){ // Dictionary for storing // the precomputed sum Dictionary<int, int> dp = new Dictionary<int, int>(); // Bases Cases dp.Add(0, 0); dp.Add(1, 1); // Check if n is not in dp then // only call the function so as // to reduce no of recursive calls if (!dp.ContainsKey(n)) dp.Add(n, 1 + Math.Min(n % 2 + count(n / 2), n % 3 + count(n / 3))); // Return the answer return dp[n];}// Driver Codepublic static void Main(String[] args){ // Given number N int N = 6; // Function call Console.WriteLine(String.Join("", (count(N))));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for // the above approach// Function to find the minimum// number to steps to reduce N to 0function count(n){ // Dictionary for storing // the precomputed sum var dp = new Map(); // Bases Cases dp.set(0, 0); dp.set(1, 1); // Check if n is not in dp then // only call the function so as // to reduce no of recursive calls if (!dp.has(n)) dp.set(n, 1 + Math.min(n % 2 + count(parseInt(n / 2)), n % 3 + count(parseInt(n / 3)))); // Return the answer return dp.get(n);}// Driver Code// Given number Nvar N = 6;// Function calldocument.write( count(N));</script> |
Output
3
Time Complexity: O(Nlog N), where N represents the given integer.
Auxiliary Space: O(N), where N represents the given integer.
Efficient approach: Using DP Tabulation method
This method Provided further improves on this by avoiding the use of a map and instead using an array to store the previously computed results. This is more efficient as array access is faster than map access.
Implementation steps :
- Create a vector dp of size n+1 and initialize dp[0] to 0 and dp[1] to 1.
- Loop from i=2 to i=n and for each i, compute the minimum number of steps to reduce i to 0 using the recurrence relation dp[i] = 1 + min(dp[i-1], dp[i/2] (if i is even), dp[i/3] (if i is divisible by 3)).
- Return dp[n] as the result.
Implementation:
C++
// C++ program for above approach#include<bits/stdc++.h>using namespace std;const int MAXN = 1e6+5;int dp[MAXN];int count(int n){ // Base Cases if(n == 0) return 0; if(n == 1) return 1; // Check if n is already computed if(dp[n] != 0) return dp[n]; // Compute the answer recursively int ans = 1 + min(n % 2 + count(n / 2), n % 3 + count(n / 3)); // Store the computed answer dp[n] = ans; // Return the answer return ans;}int main(){ // Given number N int N = 6; // Initialize the dp array to 0 memset(dp, 0, sizeof(dp)); // Function call cout << count(N);}// this code is contributed by bhardwajji |
Java
// Java program for above approachimport java.util.*;class Main { static int[] dp = new int[(int)1e6 + 5]; public static int count(int n) { // Base Cases if (n == 0) return 0; if (n == 1) return 1; // Check if n is already computed if (dp[n] != 0) return dp[n]; // Compute the answer recursively int ans = 1 + Math.min(n % 2 + count(n / 2), n % 3 + count(n / 3)); // Store the computed answer dp[n] = ans; // Return the answer return ans; } public static void main(String[] args) { // Given number N int N = 6; // Initialize the dp array to 0 Arrays.fill(dp, 0); // Function call System.out.println(count(N)); }}// This code is contributed by sarojmcy2e |
Python3
MAXN = 1000005dp = [0] * MAXNdef count(n): # Base Cases if n == 0: return 0 if n == 1: return 1 # Check if n is already computed if dp[n] != 0: return dp[n] # Compute the answer recursively ans = 1 + min(n % 2 + count(n // 2), n % 3 + count(n // 3)) # Store the computed answer dp[n] = ans # Return the answer return ans# Given number NN = 6# Initialize the dp array to 0dp = [0] * MAXN# Function callprint(count(N)) |
C#
using System;class MainClass {const int MAXN = 1000005;static int[] dp = new int[MAXN]; static int count(int n) { // Base Cases if (n == 0) return 0; if (n == 1) return 1; // Check if n is already computed if (dp[n] != 0) return dp[n]; // Compute the answer recursively int ans = 1 + Math.Min(n % 2 + count(n / 2), n % 3 + count(n / 3)); // Store the computed answer dp[n] = ans; // Return the answer return ans;}public static void Main() { // Given number N int N = 6; // Initialize the dp array to 0 Array.Fill(dp, 0); // Function call Console.WriteLine(count(N));}} |
Javascript
// Javascript program for above approachlet dp = new Array(1000005).fill(0);function count(n) { // Base Cases if (n == 0) return 0; if (n == 1) return 1; // Check if n is already computed if (dp[n] != 0) return dp[n]; // Compute the answer recursively let ans = 1 + Math.min(n % 2 + count(Math.floor(n / 2)), n % 3 + count(Math.floor(n / 3))); // Store the computed answer dp[n] = ans; // Return the answer return ans;}// Given number Nlet N = 6;// Function callconsole.log(count(N)); |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N),
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
