Dados dos enteros M y N , la tarea es encontrar el costo mínimo para convertir M en N mediante la suma repetitiva de divisores pares del valor actual de M (excepto M).
El costo de agregar un divisor par del valor actual de M, digamos d, es igual a M / d.
Imprima «-1» si es imposible convertir M a N.
Ejemplos:
Entrada: M = 6, N = 24
Salida: 10
Explicación:
Paso 1: M = 6 + 2 = 8, Costo = (6 / 2) = 3
Paso 2: M = 8 + 4 = 12, Costo = 3 + ( 8 / 2) = 5
Paso 3: M = 12 + 6 = 18, Costo = 5 + (12/ 6) = 7
Paso 4: M = 18 + 6 = 24, Costo = 7 + (18 / 6) = 10
Por lo tanto, el costo mínimo para convertir M en N es igual a 10.Entrada: M = 9, N = 17
Salida: -1
Explicación:
Dado que no hay divisores pares de 9, la conversión no es posible.
Enfoque ingenuo : el enfoque más simple es iterar a través de todos los divisores pares posibles de un número dado M y calcular recursivamente el costo mínimo para cambiar M a N. La relación de recurrencia formada viene dada por:
min_cost = Math.min(min_cost, m / i + minSteps(m + i, n))
A continuación se muestra la implementación del enfoque anterior:
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 n
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 = min(min_cost,
m / i +
minSteps(m + i, n));
}
}
// Return min_cost
return min_cost;
}
// Driver code
int 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 approach
import 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 approach inf = 1000000008 # Function to find the value of # minimum steps to convert m to n def 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 Code if __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 approach
using 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 approach
let 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>
Producción:
10
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica y memorización para la implementación anterior. En lugar de calcular los estados una y otra vez, guárdelo en una array dp[] y utilícelo cuando sea necesario.
dp(m) = min(dp(m), (m/i) + dp(m+i)) para todos los divisores pares de m menores que m
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
int inf = 1000000008;
// Utility function to calculate the
// minimum cost
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 = 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 code
int main()
{
int M = 6;
int N = 24;
// Function call
minSteps(M, N);
}
// This code is contributed by akhilsaini
Java
// Java program for the above approach
import 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 approach
using System;
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];
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 approach inf = 1000000008; # Utility function to calculate the # minimum cost def 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 code if __name__ == '__main__': M = 6; N = 24; # Function Call minSteps(M, N); # This code contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
var inf = 1000000008;
// Utility function to calculate the
// minimum cost
function 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 code
var M = 6;
var N = 24;
// Function call
minSteps(M, N);
// This code is contributed by itsok.
</script>
Producción:
10
Complejidad temporal: O(Nlog(M))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA