Sunday, June 13, 2021

Published June 13, 2021 by Anonymous with 0 comment

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

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

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++

#include <bits/stdc++.h>

using namespace std;

  

int findMinOperations(int n)

{

    

    int i, dp[n + 1];

  

    for (i = 0; i < n + 1; i++) {

        dp[i] = 999999;

    }

  

    

    dp[2] = 0;

  

    

    for (i = 2; i < n + 1; i++) {

  

        

        if (i * 5 <= n) {

  

            dp[i * 5] = min(

dp[i * 5], dp[i] + 1);

        }

  

        

        if (i + 3 <= n) {

  

            dp[i + 3] = min(

dp[i + 3], dp[i] + 1);

        }

    }

  

    

    return dp[n];

}

  

int main()

{

    

    int n = 28;

  

    

    int m = findMinOperations(n);

  

    

    if (m != 9999)

        cout << m;

    else

        cout << -1;

  

    return 0;

}

Time Complexity: O(n)
Auxiliary Space: O(n)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.


Adblock test (Why?)


Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets
      edit

0 comments:

Post a Comment