Saturday, 23 Oct 2021

# Minimum number of given operations required to reduce a number to 2

Minimum number of given operations required to reduce a number to 2Given 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 = 28Output: 3Explanation: 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=10Output: 1Explanation: 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 as 0.Iterate in the range [2, n] using the variable iIf 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++#include using namespace std;int findMinOperations(int n){        int i, dp[n + 1];    for (i = 0; i < n + 1; i++) {        dp[i] = 999999;    }        dp = 0;        for (i = 2; i < n + 1; i++) {                if (i * 5