Given a positive integer N, the task is to find the minimum number of operations needed to convert N to 2 either by decrementing N by 3 or dividing N by 5 if N is divisible by 5. If it is not possible to reduce N to 2, then print “-1”.
Examples:
Input: N =10
Output: 1
Explanation:
Following are the operations performed to reduce N to 2:
- Dividing N by 5, reduces N to 10/5 = 2.
After the above operations, N is reduced to 2. Therefore, the minimum number of operations required is 1.
Input: N = 25
Output: 2
Approach: The given problem can be solved by using Dynamic Programming, the idea is to start iterating from 2 and perform both the operations in a reverse manner i.e., instead of subtracting, perform addition of 3 and instead of dividing, perform multiplication with 5 at every state and store the minimum number of operations for every possible value of N in the array dp[].
If the value of N is reached, then print the value of dp[N] as the minimum number of operations. Otherwise, print -1. Follow the steps below to solve the problem:
- Initialize an auxiliary array, say dp[] of size (N + 1), and initialize all array elements with INT_MAX.
- Set the value of dp[2] equal to 0.
- Iterate over the range [0, N], and update the value of dp[i] as:
- dp[i * 5] = min(dp[i * 5], dp[i] + 1).
- dp[i + 3] = min(dp[i + 3], dp[i] + 1).
- If the value of dp[N] is INT_MAX, then print -1. Otherwise, print dp[N] as the result.
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// of operations to reduce N to 2 by// dividing N by 5 or decrementing by 3int minimumOperations(int N){ // Initialize the dp array int dp[N + 1]; int i; // Initialize the array dp[] for (int i = 0; i <= N; i++) { dp[i] = 1e9; } // For N = 2 number of operations // needed is zero dp[2] = 0; // Iterating over the range [1, N] for (i = 2; i <= N; i++) { // If it's not possible to // create current N if (dp[i] == 1e9) continue; // Multiply with 5 if (i * 5 <= N) { dp[i * 5] = min(dp[i * 5], dp[i] + 1); } // Adding the value 3 if (i + 3 <= N) { dp[i + 3] = min(dp[i + 3], dp[i] + 1); } } // Checking if not possible to // make the number as 2 if (dp[N] == 1e9) return -1; // Return the minimum number // of operations return dp[N];}// Driver Codeint main(){ int N = 25; cout << minimumOperations(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the minimum number // of operations to reduce N to 2 by // dividing N by 5 or decrementing by 3 static int minimumOperations(int N) { // Initialize the dp array int[] dp = new int[N + 1]; int i; // Initialize the array dp[] for (i = 0; i <= N; i++) { dp[i] = (int)1e9; } // For N = 2 number of operations // needed is zero dp[2] = 0; // Iterating over the range [1, N] for (i = 2; i <= N; i++) { // If it's not possible to // create current N if (dp[i] == (int)1e9) continue; // Multiply with 5 if (i * 5 <= N) { dp[i * 5] = Math.min(dp[i * 5], dp[i] + 1); } // Adding the value 3 if (i + 3 <= N) { dp[i + 3] = Math.min(dp[i + 3], dp[i] + 1); } } // Checking if not possible to // make the number as 2 if (dp[N] == 1e9) return -1; // Return the minimum number // of operations return dp[N]; } // Driver Code public static void main(String[] args) { int N = 25; System.out.println(minimumOperations(N)); }}// This code is contributed by Potta Lokesh |
C#
// C# program for above approachusing System;class GFG{ // Function to find the minimum number // of operations to reduce N to 2 by // dividing N by 5 or decrementing by 3 static int minimumOperations(int N) { // Initialize the dp array int[] dp = new int[N + 1]; int i; // Initialize the array dp[] for (i = 0; i <= N; i++) { dp[i] = (int)1e9; } // For N = 2 number of operations // needed is zero dp[2] = 0; // Iterating over the range [1, N] for (i = 2; i <= N; i++) { // If it's not possible to // create current N if (dp[i] == (int)1e9) continue; // Multiply with 5 if (i * 5 <= N) { dp[i * 5] = Math.Min(dp[i * 5], dp[i] + 1); } // Adding the value 3 if (i + 3 <= N) { dp[i + 3] = Math.Min(dp[i + 3], dp[i] + 1); } } // Checking if not possible to // make the number as 2 if (dp[N] == 1e9) return -1; // Return the minimum number // of operations return dp[N]; }// Driver Codepublic static void Main(String[] args){ int N = 25; Console.Write(minimumOperations(N));}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program for the above approach // Function to find the minimum number // of operations to reduce N to 2 by // dividing N by 5 or decrementing by 3 function minimumOperations(N) { // Initialize the dp array let dp = new Array(N + 1); let i; // Initialize the array dp[] for (i = 0; i <= N; i++) { dp[i] = 1e9; } // For N = 2 number of operations // needed is zero dp[2] = 0; // Iterating over the range [1, N] for (i = 2; i <= N; i++) { // If it's not possible to // create current N if (dp[i] == 1e9) continue; // Multiply with 5 if (i * 5 <= N) { dp[i * 5] = Math.min(dp[i * 5], dp[i] + 1); } // Adding the value 3 if (i + 3 <= N) { dp[i + 3] = Math.min(dp[i + 3], dp[i] + 1); } } // Checking if not possible to // make the number as 2 if (dp[N] == 1e9) return -1; // Return the minimum number // of operations return dp[N]; } // Driver Code let N = 25; document.write(minimumOperations(N));// This code is contributed by sanjoy_62.</script> |
Python3
# Python 3 program for the above approach# Function to find the minimum number# of operations to reduce N to 2 by# dividing N by 5 or decrementing by 3def minimumOperations(N): # Initialize the dp array dp = [0 for i in range(N + 1)] # Initialize the array dp[] for i in range(N+1): dp[i] = 1000000000 # For N = 2 number of operations # needed is zero dp[2] = 0 # Iterating over the range [1, N] for i in range(2,N+1,1): # If it's not possible to # create current N if (dp[i] == 1000000000): continue # Multiply with 5 if (i * 5 <= N): dp[i * 5] = min(dp[i * 5], dp[i] + 1) # Adding the value 3 if (i + 3 <= N): dp[i + 3] = min(dp[i + 3], dp[i] + 1) # Checking if not possible to # make the number as 2 if (dp[N] == 1000000000): return -1 # Return the minimum number # of operations return dp[N]# Driver Codeif __name__ == '__main__': N = 25 print(minimumOperations(N)) |
Output:
2
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!
