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:
Input: N = 9, M = 2
Output: 4
Explanation: 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 = 1
Output: 5
Approach: 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++
// C++ Program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum count of// operations to reduce N to 0 using Mint findMinimum(int N, int M){ // If N is already 0 if (N == 0) { return 0; } // Stores the minimum count of operations int ans = INT_MAX; // Loop to iterate in the range [0, √N] for (int i = 0; i * i <= N; i++) { // Edge case to prevent infinite looping if (M == 1 && i == 0) { continue; } // Stores the current count of moves int count = i; int tempN = N; // Number of operations required to // reduce N to 0 by dividing by M + i while (tempN != 0) { tempN /= (M + i); count++; } // Update the final count ans = min(count, ans); } // Return answer return ans;}// Driver codeint main(){ int N = 9; int M = 2; cout << findMinimum(N, M); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static int findMinimum(int N, int M) { // If N is already 0 if (N == 0) { return 0; } // Stores the minimum count of operations int ans = 1000000007; // Loop to iterate in the range [0, √N] for (int i = 0; i * i <= N; i++) { // Edge case to prevent infinite looping if (M == 1 && i == 0) { continue; } // Stores the current count of moves int count = i; int tempN = N; // Number of operations required to // reduce N to 0 by dividing by M + i while (tempN != 0) { tempN /= (M + i); count++; } // Update the final count if(count < ans){ ans = count; } } // Return answer return ans; } // Driver code public static void main(String[] args) { int N = 9; int M = 2; System.out.println(findMinimum(N, M)); }}// This code is contributed by maddler. |
Python3
# Python Program to implement# the above approach# Function to find the minimum count of# operations to reduce N to 0 using Mdef findMinimum(N, M): # If N is already 0 if (N == 0): return 0 # Stores the minimum count of operations ans = 10**9 # Loop to iterate in the range[0, √N] i = 0 while(i * i <= N): i += 1 # Edge case to prevent infinite looping if (M == 1 and i == 0): continue # Stores the current count of moves count = i tempN = N # Number of operations required to # reduce N to 0 by dividing by M + i while (tempN != 0): tempN = tempN // (M + i) count += 1 # Update the final count ans = min(count, ans) # Return answer return ans# Driver codeN = 9M = 2print(findMinimum(N, M))# This code is contributed by Saurabh Jaiswal |
C#
/*package whatever //do not write package name here */using System;class GFG{ public static int findMinimum(int N, int M) { // If N is already 0 if (N == 0) { return 0; } // Stores the minimum count of operations int ans = 1000000007; // Loop to iterate in the range [0, √N] for (int i = 0; i * i <= N; i++) { // Edge case to prevent infinite looping if (M == 1 && i == 0) { continue; } // Stores the current count of moves int count = i; int tempN = N; // Number of operations required to // reduce N to 0 by dividing by M + i while (tempN != 0) { tempN /= (M + i); count++; } // Update the final count if (count < ans) { ans = count; } } // Return answer return ans; } // Driver code public static void Main() { int N = 9; int M = 2; Console.WriteLine(findMinimum(N, M)); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum count of // operations to reduce N to 0 using M function findMinimum(N, M) { // If N is already 0 if (N == 0) { return 0; } // Stores the minimum count of operations let ans = Number.MAX_VALUE; // Loop to iterate in the range [0, √N] for (let i = 0; i * i <= N; i++) { // Edge case to prevent infinite looping if (M == 1 && i == 0) { continue; } // Stores the current count of moves let count = i; let tempN = N; // Number of operations required to // reduce N to 0 by dividing by M + i while (tempN != 0) { tempN = Math.floor(tempN / (M + i)); count++; } // Update the final count ans = Math.min(count, ans); } // Return answer return ans; } // Driver code let N = 9; let M = 2; document.write(findMinimum(N, M)); // This code is contributed by Potta Lokesh </script> |
Output
4
Time complexity: O(√N*log N )
Auxiliary Space: O(1)
