Dados dos números N y M , la tarea es encontrar las operaciones mínimas necesarias para convertir N en M sumándolo repetidamente con todos los divisores pares de N excepto N . Imprime -1 si la conversión no es posible.
Ejemplos:
Entrada: N = 6, M = 24
Salida: 4
Explicación:
Paso 1: Sume 2 (2 es un divisor par y 2! = 6) a 6. Ahora N se convierte en 8.
Paso 2: Sume 4 (4 es un divisor par y 4 != 8) a 8. Ahora N se convierte en 12.
Paso 3: Sume 6 (6 es un divisor par y 6!=12) a 12. Ahora N se convierte en 18.
Paso 4: Sume 6 (6 es un divisor par y 6!= 18) a 18. Ahora N se convierte en 24 = M.
Por lo tanto, se necesitan 4 pasos.Entrada: N = 9, M = 17
Salida: -1
Explicación:
No hay divisores pares para sumar 9, por lo que no podemos convertir N en M.
Enfoque ingenuo: la solución más simple es considerar todos los posibles divisores pares de un número y calcular la respuesta para ellos recursivamente y finalmente devolver el mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// INF is the maximum value
// which indicates Impossible state
const int INF = 1e7;
// Recursive Function that considers
// all possible even divisors of cur
int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
// Return 0 if cur == M
if (cur == M)
return 0;
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// means we can't transform cur to M
int op = INF;
// Loop to find even divisors of cur
for (int i = 2; i * i <= cur; i++) {
// if i is divisor of cur
if (cur % i == 0) {
// if i is even
if (i % 2 == 0) {
// Finding divisors
// recursively for cur+i
op = min(op,
1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i
&& (cur / i) % 2 == 0) {
// Find recursively
// for cur+(cur/i)
op = min(
op,
1 + min_op(
cur + (cur / i),
M));
}
}
}
// Return the answer
return op;
}
// Function that finds the minimum
// operation to reduce N to M
int min_operations(int N, int M)
{
int op = min_op(N, M);
// INF indicates impossible state
if (op >= INF)
cout << "-1";
else
cout << op << "\n";
}
// Driver Code
int main()
{
// Given N and M
int N = 6, M = 24;
// Function Call
min_operations(N, M);
return 0;
}
Java
// Java program for the above approach
class GFG{
// INF is the maximum value
// which indicates Impossible state
static int INF = (int) 1e7;
// Recursive Function that considers
// all possible even divisors of cur
static int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
// Return 0 if cur == M
if (cur == M)
return 0;
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// means we can't transform cur to M
int op = INF;
// Loop to find even divisors of cur
for (int i = 2; i * i <= cur; i++)
{
// if i is divisor of cur
if (cur % i == 0)
{
// if i is even
if (i % 2 == 0)
{
// Finding divisors
// recursively for cur+i
op = Math.min(op, 1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i && (cur / i) % 2 == 0)
{
// Find recursively
// for cur+(cur/i)
op = Math.min(op, 1 + min_op(
cur + (cur / i), M));
}
}
}
// Return the answer
return op;
}
// Function that finds the minimum
// operation to reduce N to M
static void min_operations(int N, int M)
{
int op = min_op(N, M);
// INF indicates impossible state
if (op >= INF)
System.out.print("-1");
else
System.out.print(op + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given N and M
int N = 6, M = 24;
// Function Call
min_operations(N, M);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
# INF is the maximum value
# which indicates Impossible state
INF = int(1e7);
# Recursive Function that considers
# all possible even divisors of cur
def min_op(cur, M):
# Indicates impossible state
if (cur > M):
return INF;
# Return 0 if cur == M
if (cur == M):
return 0;
# op stores the minimum operations
# required to transform cur to M
# Initially it is set to INF that
# means we can't transform cur to M
op = int(INF);
# Loop to find even divisors of cur
for i in range(2, int(cur ** 1 / 2) + 1):
# If i is divisor of cur
if (cur % i == 0):
# If i is even
if (i % 2 == 0):
# Finding divisors
# recursively for cur+i
op = min(op, 1 + min_op(cur + i, M));
# Check another divisor
if ((cur / i) != i and
(cur / i) % 2 == 0):
# Find recursively
# for cur+(cur/i)
op = min(op, 1 + min_op(
cur + (cur // i), M));
# Return the answer
return op;
# Function that finds the minimum
# operation to reduce N to M
def min_operations(N, M):
op = min_op(N, M);
# INF indicates impossible state
if (op >= INF):
print("-1");
else:
print(op);
# Driver Code
if __name__ == '__main__':
# Given N and M
N = 6;
M = 24;
# Function call
min_operations(N, M);
# This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
class GFG {
// INF is the maximum value
// which indicates Impossible state
static int INF = (int)1e7;
// Recursive Function that considers
// all possible even divisors of cur
static int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
// Return 0 if cur == M
if (cur == M)
return 0;
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// means we can't transform cur to M
int op = INF;
// Loop to find even divisors of cur
for (int i = 2; i * i <= cur; i++)
{
// if i is divisor of cur
if (cur % i == 0)
{
// if i is even
if (i % 2 == 0)
{
// Finding divisors
// recursively for cur+i
op = Math.Min(op,1 +
min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i && (cur / i) % 2 == 0)
{
// Find recursively
// for cur+(cur/i)
op = Math.Min(op, 1 +
min_op(cur +
(cur / i), M));
}
}
}
// Return the answer
return op;
}
// Function that finds the minimum
// operation to reduce N to M
static void min_operations(int N, int M)
{
int op = min_op(N, M);
// INF indicates impossible state
if (op >= INF)
Console.Write("-1");
else
Console.Write(op + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given N and M
int N = 6, M = 24;
// Function Call
min_operations(N, M);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// INF is the maximum value
// which indicates Impossible state
let INF = 1e7;
// Recursive Function that considers
// all possible even divisors of cur
function min_op(cur, M)
{
// Indicates impossible state
if (cur > M)
return INF;
// Return 0 if cur == M
if (cur == M)
return 0;
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// means we can't transform cur to M
let op = INF;
// Loop to find even divisors of cur
for (let i = 2; i * i <= cur; i++)
{
// if i is divisor of cur
if (cur % i == 0)
{
// if i is even
if (i % 2 == 0)
{
// Finding divisors
// recursively for cur+i
op = Math.min(op, 1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i && (cur / i) % 2 == 0)
{
// Find recursively
// for cur+(cur/i)
op = Math.min(op, 1 + min_op(
cur + (cur / i), M));
}
}
}
// Return the answer
return op;
}
// Function that finds the minimum
// operation to reduce N to M
function min_operations(N, M)
{
let op = min_op(N, M);
// INF indicates impossible state
if (op >= INF)
document.write("-1");
else
document.write(op + "\n");
}
// Driver Code
// Given N and M
let N = 6, M = 24;
// Function Call
min_operations(N, M);
</script>
Producción:
4
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es utilizar la programación dinámica y almacenar el estado de los subproblemas superpuestos en el enfoque ingenuo para calcular la respuesta de manera eficiente. Siga los pasos a continuación para resolver el problema:
- Inicialice una tabla dp dp[i] = -1 para todo N≤i≤M .
- Considere todos los posibles divisores pares de un número y encuentre el mínimo de todos ellos.
- Finalmente, almacene el resultado en dp[] y devuelva la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// INF is the maximum value
// which indicates Impossible state
const int INF = 1e7;
const int max_size = 100007;
// Stores the dp states
int dp[max_size];
// Recursive Function that considers
// all possible even divisors of cur
int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
if (cur == M)
return 0;
// Check dp[cur] is already
// calculated or not
if (dp[cur] != -1)
return dp[cur];
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// meanswe cur can't be transform to M
int op = INF;
// Loop to find even divisors of cur
for (int i = 2; i * i <= cur; i++) {
// if i is divisor of cur
if (cur % i == 0) {
// if i is even
if (i % 2 == 0) {
// Find recursively
// for cur+i
op = min(op, 1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i && (cur / i) % 2 == 0) {
// Find recursively
// for cur+(cur/i)
op = min(op,
1 + min_op(cur + (cur / i), M));
}
}
}
// Finally store the current state
// result and return the answer
return dp[cur] = op;
}
// Function that counts the minimum
// operation to reduce N to M
int min_operations(int N, int M)
{
// Initialise dp state
for (int i = N; i <= M; i++) {
dp[i] = -1;
}
// Function Call
return min_op(N, M);
}
// Driver Code
int main()
{
// Given N and M
int N = 6, M = 24;
// Function Call
int op = min_operations(N, M);
// INF indicates impossible state
if (op >= INF)
cout << "-1";
else
cout << op << "\n";
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// INF is the maximum value
// which indicates Impossible state
static int INF = (int) 1e7;
static int max_size = 100007;
// Stores the dp states
static int []dp = new int[max_size];
// Recursive Function that considers
// all possible even divisors of cur
static int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
if (cur == M)
return 0;
// Check dp[cur] is already
// calculated or not
if (dp[cur] != -1)
return dp[cur];
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// meanswe cur can't be transform to M
int op = INF;
// Loop to find even divisors of cur
for(int i = 2; i * i <= cur; i++)
{
// If i is divisor of cur
if (cur % i == 0)
{
// If i is even
if (i % 2 == 0)
{
// Find recursively
// for cur+i
op = Math.min(op,
1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i &&
(cur / i) % 2 == 0)
{
// Find recursively
// for cur+(cur/i)
op = Math.min(op,
1 + min_op(cur + (cur / i), M));
}
}
}
// Finally store the current state
// result and return the answer
return dp[cur] = op;
}
// Function that counts the minimum
// operation to reduce N to M
static int min_operations(int N, int M)
{
// Initialise dp state
for(int i = N; i <= M; i++)
{
dp[i] = -1;
}
// Function call
return min_op(N, M);
}
// Driver Code
public static void main(String[] args)
{
// Given N and M
int N = 6, M = 24;
// Function call
int op = min_operations(N, M);
// INF indicates impossible state
if (op >= INF)
System.out.print("-1");
else
System.out.print(op + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the # above approach # INF is the maximum value # which indicates Impossible state INF = 10000007; max_size = 100007; # Stores the dp states dp = [0 for i in range(max_size)]; # Recursive Function # that considers all # possible even divisors # of cur def min_op(cur, M): # Indicates impossible # state if (cur > M): return INF; if (cur == M): return 0; # Check dp[cur] is already # calculated or not if (dp[cur] != -1): return dp[cur]; # op stores the minimum # operations required to # transform cur to M # Initially it is set # to INF that meanswe cur # can't be transform to M op = INF; i = 2 # Loop to find even # divisors of cur while(i * i <= cur): # if i is divisor of cur if (cur % i == 0): # if i is even if(i % 2 == 0): # Find recursively # for cur+i op = min(op, 1 + min_op(cur + i, M)); # Check another divisor if ((cur // i) != i and (cur // i) % 2 == 0): # Find recursively # for cur+(cur/i) op = min(op, 1 + min_op(cur + (cur // i), M)) i += 1 # Finally store the current state # result and return the answer dp[cur] = op; return op # Function that counts the minimum # operation to reduce N to M def min_operations(N, M): # Initialise dp state for i in range(N, M + 1): dp[i] = -1; # Function Call return min_op(N, M); # Driver code if __name__ == "__main__": # Given N and M N = 6 M = 24 # Function Call op = min_operations(N, M); # INF indicates impossible state if (op >= INF): print(-1) else: print(op) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
// INF is the maximum value
// which indicates Impossible state
static int INF = (int) 1e7;
static int max_size = 100007;
// Stores the dp states
static int []dp = new int[max_size];
// Recursive Function that considers
// all possible even divisors of cur
static int min_op(int cur, int M)
{
// Indicates impossible state
if (cur > M)
return INF;
if (cur == M)
return 0;
// Check dp[cur] is already
// calculated or not
if (dp[cur] != -1)
return dp[cur];
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// meanswe cur can't be transform to M
int op = INF;
// Loop to find even divisors of cur
for(int i = 2; i * i <= cur; i++)
{
// If i is divisor of cur
if (cur % i == 0)
{
// If i is even
if (i % 2 == 0)
{
// Find recursively
// for cur+i
op = Math.Min(op, 1 +
min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i &&
(cur / i) % 2 == 0)
{
// Find recursively
// for cur+(cur/i)
op = Math.Min(op, 1 +
min_op(cur +
(cur / i), M));
}
}
}
// Finally store the current state
// result and return the answer
return dp[cur] = op;
}
// Function that counts the minimum
// operation to reduce N to M
static int min_operations(int N,
int M)
{
// Initialise dp state
for(int i = N; i <= M; i++)
{
dp[i] = -1;
}
// Function call
return min_op(N, M);
}
// Driver Code
public static void Main(String[] args)
{
// Given N and M
int N = 6, M = 24;
// Function call
int op = min_operations(N, M);
// INF indicates impossible state
if (op >= INF)
Console.Write("-1");
else
Console.Write(op + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// INF is the maximum value
// which indicates Impossible state
var INF = 10000000;
var max_size = 100007;
// Stores the dp states
var dp = Array(max_size);
// Recursive Function that considers
// all possible even divisors of cur
function min_op( cur, M)
{
// Indicates impossible state
if (cur > M)
return INF;
if (cur == M)
return 0;
// Check dp[cur] is already
// calculated or not
if (dp[cur] != -1)
return dp[cur];
// op stores the minimum operations
// required to transform cur to M
// Initially it is set to INF that
// meanswe cur can't be transform to M
var op = INF;
// Loop to find even divisors of cur
for (var i = 2; i * i <= cur; i++) {
// if i is divisor of cur
if (cur % i == 0) {
// if i is even
if (i % 2 == 0) {
// Find recursively
// for cur+i
op = Math.min(op, 1 + min_op(cur + i, M));
}
// Check another divisor
if ((cur / i) != i && (cur / i) % 2 == 0) {
// Find recursively
// for cur+(cur/i)
op = Math.min(op,
1 + min_op(cur + (cur / i), M));
}
}
}
// Finally store the current state
// result and return the answer
return dp[cur] = op;
}
// Function that counts the minimum
// operation to reduce N to M
function min_operations(N, M)
{
// Initialise dp state
for ( i = N; i <= M; i++) {
dp[i] = -1;
}
// Function Call
return min_op(N, M);
}
// Driver Code
// Given N and M
var N = 6, M = 24;
// Function Call
var op = min_operations(N, M);
// INF indicates impossible state
if (op >= INF)
document.write( "-1");
else
document.write( op + "<br>");
// This code is contributed by noob2000.
</script>
Producción:
4
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(M)