Given two integers M and N, the task is to find the minimum cost to convert M to N by repetitive addition of even divisors of the current value of M (except M).
The cost to add an even divisor of the current value of M, say d, is equal to M / d.
Print “-1” if it is impossible to convert M to N.
Examples:
Input: M = 6, N = 24
Output: 10
Explanation:
Step 1: M = 6 + 2 = 8, Cost = (6 / 2) = 3
Step 2: M = 8 + 4 = 12, Cost = 3 + (8 / 2) = 5
Step 3: M = 12 + 6 = 18, Cost = 5 + (12/ 6) = 7
Step 4: M = 18 + 6 = 24, Cost = 7 + (18 / 6) = 10
Therefore, the minimum cost to convert M to N is equal to 10.Input: M = 9, N = 17
Output: -1
Explanation:
Since there are no even divisors of 9, therefore, conversion is not possible.
Naive approach: The simplest approach is to iterate through all possible even divisors of given number M and recursively calculate the minimum cost to change M to N. The recurrence relation formed is given by:
min_cost = Math.min(min_cost, m / i + minSteps(m + i, n))
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <iostream>using namespace std;int inf = 1000000008;// Function to find the value of// minimum steps to convert m to nint minSteps(int m, int n){ // Base Case if (n == m) return 0; // If n exceeds m if (m > n) return inf; int min_cost = inf; // Iterate through all possible // even divisors of m for(int i = 2; i < m; i += 2) { // If m is divisible by i, // then find the minimum cost if (m % i == 0) { // Add the cost to convert // m to m+i and recursively // call next state min_cost = min(min_cost, m / i + minSteps(m + i, n)); } } // Return min_cost return min_cost;}// Driver codeint main(){ int M = 6; int N = 24; // Function call int minimum_cost = minSteps(M, N); // If conversion is // not possible if (minimum_cost == inf) minimum_cost = -1; // Print the cost cout << minimum_cost; return 0;}// This code is contributed by akhilsaini |
Java
// Java program for the above approachimport java.util.*;public class GFG { static int inf = 1000000008; // Function to find the value of // minimum steps to convert m to n public static int minSteps(int m, int n) { // Base Case if (n == m) return 0; // If n exceeds m if (m > n) return inf; int min_cost = inf; // Iterate through all possible // even divisors of m for (int i = 2; i < m; i += 2) { // If m is divisible by i, // then find the minimum cost if (m % i == 0) { // Add the cost to convert // m to m+i and recursively // call next state min_cost = Math.min( min_cost, m / i + minSteps(m + i, n)); } } // Return min_cost return min_cost; } // Driver Code public static void main(String args[]) { int M = 6; int N = 24; // Function Call int minimum_cost = minSteps(M, N); // If conversion is // not possible minimum_cost = minimum_cost == inf ? -1 : minimum_cost; // Print the cost System.out.println(minimum_cost); }} |
Python3
# Python3 program for the above approachinf = 1000000008# Function to find the value of# minimum steps to convert m to ndef minSteps(m, n): # Base Case if (n == m): return 0 # If n exceeds m if (m > n): return inf min_cost = inf # Iterate through all possible # even divisors of m for i in range(2, m, 2): # If m is divisible by i, # then find the minimum cost if (m % i == 0): # Add the cost to convert # m to m+i and recursively # call next state min_cost = min(min_cost, m / i + minSteps(m + i, n)) # Return min_cost return min_cost# Driver Codeif __name__ == '__main__': M = 6 N = 24 # Function call minimum_cost = minSteps(M, N) # If conversion is # not possible if minimum_cost == inf: minimum_cost = -1 # Print the cost print(minimum_cost) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ static int inf = 1000000008; // Function to find the value of // minimum steps to convert m to n public static int minSteps(int m, int n) { // Base Case if (n == m) return 0; // If n exceeds m if (m > n) return inf; int min_cost = inf; // Iterate through all possible // even divisors of m for (int i = 2; i < m; i += 2) { // If m is divisible by i, // then find the minimum cost if (m % i == 0) { // Add the cost to convert // m to m+i and recursively // call next state min_cost = Math.Min(min_cost, m / i + minSteps(m + i, n)); } } // Return min_cost return min_cost; } // Driver Code public static void Main(String []args) { int M = 6; int N = 24; // Function Call int minimum_cost = minSteps(M, N); // If conversion is // not possible minimum_cost = minimum_cost == inf ? -1 : minimum_cost; // Print the cost Console.WriteLine(minimum_cost); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to implement// the above approachlet inf = 1000000008; // Function to find the value of // minimum steps to convert m to n function minSteps(m, n) { // Base Case if (n == m) return 0; // If n exceeds m if (m > n) return inf; let min_cost = inf; // Iterate through all possible // even divisors of m for (let i = 2; i < m; i += 2) { // If m is divisible by i, // then find the minimum cost if (m % i == 0) { // Add the cost to convert // m to m+i and recursively // call next state min_cost = Math.min( min_cost, m / i + minSteps(m + i, n)); } } // Return min_cost return min_cost; } // Driver Code let M = 6; let N = 24; // Function Call let minimum_cost = minSteps(M, N); // If conversion is // not possible minimum_cost = minimum_cost == inf ? -1 : minimum_cost; // Print the cost document.write(minimum_cost); </script> |
Output:
10
Time Complexity: O(2N)
Auxiliary Space: O(2N) for recursive call stack
Efficient Approach: The above approach can be optimized by using dynamic programming and memoization to the above implementation. Instead of computing the states again and again store it in an array dp[] and use it when required.
dp(m) = min(dp(m), (m/i) + dp(m+i)) for all even divisors of m less than m
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;int inf = 1000000008;// Utility function to calculate the// minimum costint minStepsUtil(int m, int n, int dp[]){ // Positive base case if (n == m) return 0; // Negative base case if (m > n) return inf; // If current state is already // computed then return the // current state value if (dp[m] != inf) return dp[m]; int min_cost = inf; // Iterate through all possible // even divisors for(int i = 2; i < m; i += 2) { if (m % i == 0) { min_cost = min(min_cost, m / i + minStepsUtil(m + i, n, dp)); } } // Store the precomputed answer return dp[m] = min_cost;}void minSteps(int M, int N){ // Initialise the dp array // with infinity int dp[N + 5]; for(int i = 0; i < N + 5; i++) { dp[i] = inf; } // Function call int minimum_cost = minStepsUtil(M, N, dp); if (minimum_cost == inf) minimum_cost = -1; // Print the minimum cost cout << minimum_cost;}// Driver codeint main(){ int M = 6; int N = 24; // Function call minSteps(M, N);}// This code is contributed by akhilsaini |
Java
// Java program for the above approachimport java.util.*;public class GFG { static int inf = 1000000008; // Utility function to calculate the // minimum cost public static int minStepsUtil(int m, int n, int dp[]) { // Positive base case if (n == m) return 0; // Negative base case if (m > n) return inf; // If current state is already // computed then return the // current state value if (dp[m] != inf) return dp[m]; int min_cost = inf; // Iterate through all possible // even divisors for (int i = 2; i < m; i += 2) { if (m % i == 0) { min_cost = Math.min( min_cost, m / i + minStepsUtil(m + i, n, dp)); } } // Store the precomputed answer return dp[m] = min_cost; } public static void minSteps(int M, int N) { // Initialise the dp array // with infinity int dp[] = new int[N + 5]; Arrays.fill(dp, inf); // Function Call int minimum_cost = minStepsUtil(M, N, dp); minimum_cost = minimum_cost == inf ? -1 : minimum_cost; // Print the minimum cost System.out.println(minimum_cost); } // Driver code public static void main(String args[]) { int M = 6; int N = 24; // Function Call minSteps(M, N); }} |
C#
// C# program for the above approachusing System;class GFG{static int inf = 1000000008;// Utility function to calculate the// minimum costpublic static int minStepsUtil(int m, int n, int []dp){ // Positive base case if (n == m) return 0; // Negative base case if (m > n) return inf; // If current state is already // computed then return the // current state value if (dp[m] != inf) return dp[m]; int min_cost = inf; // Iterate through all possible // even divisors for (int i = 2; i < m; i += 2) { if (m % i == 0) { min_cost = Math.Min(min_cost, m / i + minStepsUtil(m + i, n, dp)); } } // Store the precomputed answer return dp[m] = min_cost; } public static void minSteps(int M, int N) { // Initialise the dp array // with infinity int []dp = new int[N + 5]; for(int i = 0; i < dp.GetLength(0); i++) dp[i] = inf; // Function Call int minimum_cost = minStepsUtil(M, N, dp); minimum_cost = minimum_cost == inf ? -1 : minimum_cost; // Print the minimum cost Console.WriteLine(minimum_cost); } // Driver code public static void Main(String []args) { int M = 6; int N = 24; // Function Call minSteps(M, N); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approachinf = 1000000008;# Utility function to calculate the# minimum costdef minStepsUtil(m, n, dp): # Positive base case if (n == m): return 0; # Negative base case if (m > n): return inf; # If current state is already # computed then return the # current state value if (dp[m] != inf): return dp[m]; min_cost = inf; # Iterate through all possible # even divisors for i in range(2,m,2): if (m % i == 0): min_cost = min(min_cost, m // i + minStepsUtil(m + i, n, dp)); # Store the precomputed answer dp[m] = min_cost return dp[m];def minSteps(M, N): # Initialise the dp array # with infinity dp = [inf]*(N + 5); # Function Call minimum_cost = minStepsUtil(M, N, dp); minimum_cost = -1 if minimum_cost == inf else minimum_cost; # Print the minimum cost print(minimum_cost);# Driver codeif __name__ == '__main__': M = 6; N = 24; # Function Call minSteps(M, N);# This code contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approachvar inf = 1000000008;// Utility function to calculate the// minimum costfunction minStepsUtil(m, n, dp){ // Positive base case if (n == m) return 0; // Negative base case if (m > n) return inf; // If current state is already // computed then return the // current state value if (dp[m] != inf) return dp[m]; var min_cost = inf; // Iterate through all possible // even divisors for(var i = 2; i < m; i += 2) { if (m % i == 0) { min_cost = Math.min(min_cost, m / i + minStepsUtil(m + i, n, dp)); } } // Store the precomputed answer return dp[m] = min_cost;}function minSteps(M, N){ // Initialise the dp array // with infinity var dp = Array(N+5); for(var i = 0; i < N + 5; i++) { dp[i] = inf; } // Function call var minimum_cost = minStepsUtil(M, N, dp); if (minimum_cost == inf) minimum_cost = -1; // Print the minimum cost document.write( minimum_cost);}// Driver codevar M = 6;var N = 24;// Function callminSteps(M, N);// This code is contributed by itsok.</script> |
Output:
10
Time Complexity: O(Nlog(M))
Auxiliary Space: O(N)
Another approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table DP to store the solution of the subproblems and initialize it with INF.
- Initialize the table DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution is present stored in dp[n].
Implementation :
C++
// C++ program for above approach#include <iostream>#include <cstring>using namespace std;const int INF = 1000000008; // Utility function to calculate the// minimum costvoid minSteps(int M, int N) { int dp[N+5]; memset(dp, INF, sizeof(dp)); // initialize dp array with INF dp[M] = 0; // base case // iterave over subproblems to get the current solution for (int i = M; i <= N; i++) { for (int j = 2; j < i; j += 2) { if (i % j == 0) { dp[i+j] = min(dp[i+j], dp[i] + i/j); } } } // return if answer is exists if (dp[N] == INF) { cout << "-1"; // no path found } else { cout << dp[N]; // print minimum cost }}// Driver Codeint main() { int M = 6; int N = 24; // function call minSteps(M, N); return 0;}// this code is contributed by bhardwajji |
Python3
INF = 1000000008# Utility function to calculate the minimum costdef minSteps(M, N): dp = [INF] * (N + 5) dp[M] = 0 # base case # iterate over subproblems to get the current solution for i in range(M, N + 1 - M): for j in range(2, i, 2): if i % j == 0: dp[i + j] = min(dp[i + j], dp[i] + i // j) # return if answer is exists if dp[N] == INF: print("-1") # no path found else: print(dp[N]) # print minimum cost# Driver CodeM = 6N = 24# function callminSteps(M, N) |
Javascript
function minSteps(M, N) { const INF = 1000000008; let dp = new Array(N+5).fill(INF); // initialize dp array with INF dp[M] = 0; // base case // iterave over subproblems to get the current solution for (let i = M; i <= N; i++) { for (let j = 2; j < i; j += 2) { if (i % j == 0) { dp[i+j] = Math.min(dp[i+j], dp[i] + i/j); } } } // return if answer is exists if (dp[N] == INF) { console.log("-1"); // no path found } else { console.log(dp[N]); // print minimum cost }}// Driver Codelet M = 6;let N = 24;// function callminSteps(M, N); |
Output
10
Time complexity: O(N*N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
