Intuition
We always need to analyze the problem carefully and obtain the key points mentioned in the statement. With the given conditions, we can observe that we always need to perform operation 2 for zero or more operations and then perform operation 1 until N is reduced to 0.
Approach
Following our intuition, we can first increase ‘M’ to a certain value, then divide ‘N’ until it becomes zero.
To reach the optimal solution, it is important to understand that, after ‘M’ is increased by √N, we can always make ‘N’ equal to zero in a maximum of 2 more operations by dividing ‘N’ by ‘M’ two times. On further increasing ‘M’, it will always take a minimum of two more operations.
The algorithm is defined below:
- Declare a variable ‘BEST’ to store the minimum number of operations.
- Let a variable ‘T’, the number of times ‘M’ will be increased so that the new value of ‘M’ will be ‘M + T’, then substitute ‘N’ with ‘N / (M+T)’ until ‘N’ becomes zero.
- Iterate over all values of ‘T’ between 0 and √N inclusive to reach the best case.
- Keep updating the variable ‘BEST’, with the minimum number of operations obtained in each iteration.
- Finally, return ‘BEST’, the required minimum number of operations.
Program
// Program to find minimum operations to reduce N to 0.
#include <iostream>
#include <climits>
using namespace std;
// Function to calculate minimum operations.
int findMinOp(int N, int M)
{
// If N is already zero.
if (N == 0)
return 0;
// Variable to keep track of best result.
int BEST = INT_MAX;
// Finding optimum solution by iterating in range [0,root(N)]
for (int T = 0; T * T <= N; T++)
{
// The case when N will never become zero.
if (T == 0 && M == 1)
continue;
// Variable to count current moves and temporarily store N.
int cnt = T, tmp = N;
// Running operation 1 until N becomes zero.
while (tmp != 0)
{
tmp /= (M + T);
cnt++;
}
// Updating the best result yet.
BEST= min(BEST, cnt);
}
// Returning the result
return BEST;
}
// Main function
int main()
{
// Variables to store inputs.
int N, M;
cout << “Enter values of N and M: “;
// Taking input of the required values.
cin >> N >> M;
// Final answer.
int minOperations = findMinOp(N, M);
cout << "Minimum Operations to Reduce N to 0 are " << minOperations;
return 0;
}
Example:
Input:
Enter values of N and M: 9 2
Output:
Minimum Operations to Reduce N to 0 are 4
Complexity Analysis
Time Complexity: O(√N * log(N)), where ‘N’ is the given number.
Explanation: In function findMinOp()
- O(√N) for the outer loop iterating through values of t,
- And log(N) for the inside loop, used to reduce N to zero with operation 1.
Space Complexity: O(1)
Explanation: As no extra space is required.
Key Takeaways
The blog discussed an interesting problem, ‘Minimum operations necessary to reduce N to 0 by substituting N with N / M or increasing M by 1’. The intuition, approach, and algorithm, along with code in C++ mentioned above are helpful to understand the problem as well as its solution. You can practice more such problems from questions related to Arrays.
If you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
38+ registered 