Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
2.1.
Example:
3.
Intuition
4.
Approach
5.
Program
5.1.
Example:
5.2.
Complexity Analysis
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Minimum Operations Necessary to Reduce N to 0 by Substituting N with N/M or Increasing M by 1

## Introduction

We all prepare hard for the interview of our favorite company, solve a lot of DSA questions, study Computer Science Fundamentals, and enhance our problem-solving skills. So in this journey, this blog will help you solve one more interesting question.

“Minimum operations necessary to reduce N to 0 by substituting N with N/M or increasing M by 1” is an observation-based question. These kinds of questions are often asked in interviews to check the candidate’s observation and intuition skills.

It is always recommended to try solving the below problem on your own before moving to the solution part.

## Problem Statement

Two integers, ‘N’ and ‘M’, are given, the task is to calculate the minimum number of operations required to reduce N to 0, where operations are described as below:

1. We can substitute ‘N’ with ‘N/M.’
2. We can increase ‘M’ by one.

### Example:

Input: N = 4, M = 2

Output: 3

Explanation: The output for this example can be obtained with the following steps:

1. Increasing M by 1, i.e. M = 2+1 = 3
2. Substituting N with N/M i.e. N = 4/3 = 1
3. Substituting N with N/M i.e. N = 1/3 = 0

So the minimum number of operations to reduce N to 0 are 3.

Input: N = 12, M = 1

Output: 5

Explanation: The output for this example can be obtained with the following steps:

1. Increasing M by 1, i.e. M = 1+1 = 2
2. Increasing M by 1, i.e. M = 2+1 = 3
3. Substituting N with N/M i.e. N = 12/3 = 4
4. Substituting N with N/M i.e. N = 4/3 = 1
5. Substituting N with N/M i.e. N = 1/3 = 0

So the minimum number of operations to reduce N to 0 are 5.

Also see, Euclid GCD Algorithm

## 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;

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!

Live masterclass