- Greedy, Mathematical

Minimum operations required to reduce N to 0 by either replacing N with N/M or incrementing M by 1

Given two integers N and M, the task is to calculate the minimum number of operations required to reduce N to 0 using the following operations:Replace N with (N/M).Increment the value of M by 1.Example:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: N = 9, M = 2Output: 4Explanation: The given example can be solved by following the below sequence of operations:In 1st operation, replace N with (N/M), i.e, N = 9/2 = 4.In 2nd operation, again replace N with N/M, i.e, N = 4/2 = 2.In 3rd operation, increment M by 1, i.e, M = M+1 = 2+1 = 3.In 4th operation, replace N with N/M, i.e, N = 2/3 = 0.Hence, the number of required operations is 4 which is the minimum possible.Input: N = 15, M = 1Output: 5Approach: The given problem can be solved by observing the fact that the most optimal choice of operations is to increment the value of M let’s say x times and then reduce the value of N to N / (M+x) until it becomes 0. To find the best case, iterate over all values of x in the range [0, √N] using a variable i and calculate the number of steps required to reduce N to 0 by dividing it by (M+i). Keep track of the minimum number of operations over all possible values of (M+i) in a variable ans, which is the required value. Below is the implementation of the above approach:C++#include using namespace std;int findMinimum(int N, int M){        if (N == 0) {        return 0;    }        int ans = INT_MAX;        for (int i = 0; i * i