Given a positive integer N, the task is to reduce N to 2 by performing the following operations minimum number of times:
- Operation 1: Divide N by 5, if N is exactly divisible by 5.
- Operation 2: Subtract 3 from N.
If it is not possible, print -1.
Examples:
Input: N = 28
Output: 3
Explanation: Operation 1: Subtract 3 from 28. Therefore, N becomes 28 – 3 = 25.
Operation 2: Divide 25 by 5. Therefore, N becomes 25 / 5 = 5.
Operation 3: Subtract 3 from 5. Therefore, N becomes 5 – 3 = 2.
Hence, the minimum number of operations required is 3.Input: n=10
Output: 1
Explanation: Operation 1: Divide 10 by 5, so n becomes 10/5=2.
Hence, the minimum operations required is 1.
Naive Approach: The idea is to recursively compute the minimum number of steps required.
- If the number is not divisible by 5, then subtract 3 from n and recur for the modified value of n, adding 1 to the result.
- Else make two recursive calls, one by subtracting 3 from n and the other by diving n by 5 and return the one with the minimum number of operations, adding 1 to the result.
Time Complexity: O(2n)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use dynamic programming. Follow these steps to solve this problem.
- Create an array, say dp[n+1] to store minimum operations and initialize all the entries with INT_MAX, where dp[i] stores the minimum number of steps required to reach 2 from i.
- Handle the base case by initializing dp[2] as 0.
- Iterate in the range [2, n] using the variable i
- If the value of i*5 ? n, then update dp[i*5] to minimum of dp[i*5] and dp[i]+1.
- If the value of i+3 ? n, then update dp[i+3] to minimum of dp[i+3] and dp[i]+1.
- Print the value of 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 required to reduce n to 2int findMinOperations(int n){ // Initialize a dp array int i, dp[n + 1]; for (i = 0; i < n + 1; i++) { dp[i] = 999999; } // Handle the base case dp[2] = 0; // Iterate in the range [2, n] for (i = 2; i < n + 1; i++) { // Check if i * 5 <= n if (i * 5 <= n) { dp[i * 5] = min(dp[i * 5], dp[i] + 1); } // Check if i + 3 <= n if (i + 3 <= n) { dp[i + 3] = min(dp[i + 3], dp[i] + 1); } } // Return the result return dp[n];}// Driver codeint main(){ // Given Input int n = 28; // Function Call int m = findMinOperations(n); // Print the result if (m != 9999) cout << m; else cout << -1; return 0;} |
Java
// Java program for the above approachpublic class GFG { // Function to find the minimum number // of operations required to reduce n to 2 static int findMinOperations(int n) { // Initialize a dp array int i = 0; int dp[] = new int[n + 1]; for (i = 0; i < n + 1; i++) { dp[i] = 999999; } // Handle the base case dp[2] = 0; // Iterate in the range [2, n] for (i = 2; i < n + 1; i++) { // Check if i * 5 <= n if (i * 5 <= n) { dp[i * 5] = Math.min(dp[i * 5], dp[i] + 1); } // Check if i + 3 <= n if (i + 3 <= n) { dp[i + 3] = Math.min(dp[i + 3], dp[i] + 1); } } // Return the result return dp[n]; } // Driver code public static void main(String[] args) { // Given Input int n = 28; // Function Call int m = findMinOperations(n); // Print the result if (m != 9999) System.out.println(m); else System.out.println(-1); }}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to find the minimum number# of operations required to reduce n to 2def findMinOperations(n): # Initialize a dp array dp = [0 for i in range(n + 1)] for i in range(n + 1): dp[i] = 999999 # Handle the base case dp[2] = 0 # Iterate in the range [2, n] for i in range(2, n + 1): # Check if i * 5 <= n if (i * 5 <= n): dp[i * 5] = min(dp[i * 5], dp[i] + 1) # Check if i + 3 <= n if (i + 3 <= n): dp[i + 3] = min(dp[i + 3], dp[i] + 1) # Return the result return dp[n]# Driver codeif __name__ == '__main__': # Given Input n = 28 # Function Call m = findMinOperations(n) # Print the result if (m != 9999): print (m) else: print (-1)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the minimum number// of operations required to reduce n to 2static int findMinOperations(int n){ // Initialize a dp array int i; int []dp = new int[n + 1]; for(i = 0; i < n + 1; i++) { dp[i] = 999999; } // Handle the base case dp[2] = 0; // Iterate in the range [2, n] for(i = 2; i < n + 1; i++) { // Check if i * 5 <= n if (i * 5 <= n) { dp[i * 5] = Math.Min(dp[i * 5], dp[i] + 1); } // Check if i + 3 <= n if (i + 3 <= n) { dp[i + 3] = Math.Min(dp[i + 3], dp[i] + 1); } } // Return the result return dp[n];}// Driver codepublic static void Main(){ // Given Input int n = 28; // Function Call int m = findMinOperations(n); // Print the result if (m != 9999) Console.Write(m); else Console.Write(-1);}} // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum number // of operations required to reduce n to 2function findMinOperations(n){ // Initialize a dp array let i = 0; let dp = new Array(n + 1); for (i = 0; i < n + 1; i++) { dp[i] = 999999; } // Handle the base case dp[2] = 0; // Iterate in the range [2, n] for (i = 2; i < n + 1; i++) { // Check if i * 5 <= n if (i * 5 <= n) { dp[i * 5] = Math.min(dp[i * 5], dp[i] + 1); } // Check if i + 3 <= n if (i + 3 <= n) { dp[i + 3] = Math.min(dp[i + 3], dp[i] + 1); } } // Return the result return dp[n];}// Driver code// Given Inputlet n = 28;// Function Calllet m = findMinOperations(n);// Print the resultif (m != 9999) document.write(m);else document.write(-1);// This code is contributed by unknown2108</script> |
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!
