Reduce N to 1 by given operations
Given an integer N. Then your task is to output a minimum number of operations to reduce N into 1. You can below operations to do the same:
- Subtract 1 from N
- Update N to N/2, if N is divisible by 2
- Update N to N/3, if N is divisible by 3
Examples:
Input: N = 10
Output: 3
Explanation: The operations are performed as:
- First Operation: Subtract 1 form 10. Updated value of N = 9.
- Second Operation: N = 9 is divisible by 3. Update N as 9/3 = 3
- Second Operation: N = 3 is divisible by 3. Update N as 3/3 = 1
Now N is reduced into 1 by following sequence of N’s value as {10 → 9 → 3 → 1}. Thus, minimum number of operations required are 3.
Input: 4
Output: 2
Explanation: 4 can be reduced into 1 with two ways {4 → 3 → 1} or {4 → 2 → 1}. Both requires minimum operations as 2.
Approach: Implement the idea below to solve the problem
In this problem we have 3 choices to perform operations, in solving choice-based problems we can use Dynamic Programming. For this problem we will take help of Dynamic Programming in the form of map and for each value of N, we can explore all the given conditions and can proceed further with minimum of them.
Steps were taken to solve the problem:
- Initialize a map let say DP.
- Definition of recursive function ReduceTo1(N):
- If (N <= 1)
- Return 0
- If (map DP contains N)
- Return DP[N]
- Create a variable let say Min_op to store minimum number of operations and initialize it equal to (1+min(N % 2 + ReduceTo1(N / 2), N % 3 + ReduceTo1(N / 3)))
- DP[N] = Min_op
- Return Min_op
- If (N <= 1)
Below is the code to implement the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Map to store minimum operations for any value of N unordered_map< int , int > dp; // Function to count steps required to reduce N to 1 int ReduceTo1( int N) { // If N reduced to 1 if (N <= 1) return 0; // If steps for N already found if (dp.find(N) != dp.end()) return dp[N]; // Check the minimum steps from all given // conditions int min_op = 1 + min(N % 2 + ReduceTo1(N / 2), N % 3 + ReduceTo1(N / 3)); // Minimum steps required dp[N] = min_op; return min_op; } // Driver code int main() { // Input value of N int N = 10; // Function call cout << ReduceTo1(N); return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class ReduceTo1 { // Map to store minimum operations for any value of N static Map<Integer, Integer> dp = new HashMap<>(); // Function to count steps required to reduce N to 1 static int reduceTo1( int N) { // If N reduced to 1 if (N <= 1 ) return 0 ; // If steps for N already found if (dp.containsKey(N)) return dp.get(N); // Check the minimum steps from all given conditions int min_op = 1 + Math.min(N % 2 + reduceTo1(N / 2 ), N % 3 + reduceTo1(N / 3 )); // Minimum steps required dp.put(N, min_op); return min_op; } // Driver code public static void main(String[] args) { // Input value of N int N = 10 ; // Function call System.out.println(reduceTo1(N)); } } |
Python3
# Python Implementation # Dictionary to store minimum operations for any value of N dp = {} # Function to count steps required to reduce N to 1 def ReduceTo1(N): # If N is already 1, no steps needed if N < = 1 : return 0 # If steps for N already found if N in dp: return dp[N] # Check the minimum steps from all given conditions min_op = 1 + min (N % 2 + ReduceTo1(N / / 2 ), N % 3 + ReduceTo1(N / / 3 )) # Minimum steps required dp[N] = min_op return min_op # Driver code if __name__ = = "__main__" : # Input value of N N = 10 # Function call print (ReduceTo1(N)) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; public class ReduceTo1Example { // Dictionary to store minimum operations for any value of N static Dictionary< int , int > dp = new Dictionary< int , int >(); // Function to count steps required to reduce N to 1 static int ReduceTo1( int N) { // If N reduced to 1 if (N <= 1) return 0; // If steps for N already found if (dp.ContainsKey(N)) return dp[N]; // Check the minimum steps from all given conditions int min_op = 1 + Math.Min(N % 2 + ReduceTo1(N / 2), N % 3 + ReduceTo1(N / 3)); // Minimum steps required dp[N] = min_op; return min_op; } // Driver code public static void Main() { // Input value of N int N = 10; // Function call Console.WriteLine(ReduceTo1(N)); } } |
Javascript
// JavaScript code to implement the approach // Map to store minimum operations // for any value of N const dp = new Map(); // Function to count steps required // to reduce N to 1 function reduceTo1(N) { // If N reduced to 1 if (N <= 1) return 0; // If steps for N already found if (dp.has(N)) return dp.get(N); // Check the minimum steps from // all given conditions const min_op = 1 + Math.min(N % 2 + reduceTo1(Math.floor(N / 2)), N % 3 + reduceTo1(Math.floor(N / 3))); // Minimum steps required dp.set(N, min_op); return min_op; } // Driver code // Input value of N const N = 10; // Function call console.log(reduceTo1(N)); |
3
Time Complexity: O(Log N)
Auxiliary Space: O(Log N)
Contact Us