Dados dos números enteros N y M , la tarea es encontrar la secuencia del número mínimo de operaciones requeridas para convertir el número N en M tal que en cada operación se pueda sumar N (N = N + N) , restar como (N = N – N) , multiplicado como (N = N*N) , o dividido como (N = N/N) . Si no es posible convertir N en M , imprima «-1» .
Ejemplos:
Entrada: N = 7, M = 392
Salida: 3
+, *, +
Explicación: Las
siguientes son las operaciones realizadas:
- Realizar la suma modifica el valor de N como 7 + 7 = 14.
- Realizar la multiplicación modifica el valor de N como 14*14 = 196.
- Realizar la suma modifica el valor de N como 196 + 196 = 392.
Después de la secuencia de movimientos anterior como «+++», el valor de N se puede modificar a M.
Entrada: N = 7, M = 9
Salida: -1
Explicación: No hay una secuencia posible de operaciones para convertir N en M.
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- La operación de resta siempre dará como resultado 0 como N = N – N = 0. De manera similar, la operación de división siempre dará como resultado 1 como N = N / N = 1. Por lo tanto, estos casos se pueden manejar fácilmente.
- Para la suma y la multiplicación, el problema se puede resolver utilizando un recorrido de búsqueda primero en amplitud creando un estado para cada una de las secuencias de operaciones en orden creciente de conteo de operaciones.
Los pasos para resolver el problema planteado son los siguientes:
- Mantenga una cola para almacenar los estados BFS donde cada estado contiene el número entero alcanzable actual N’ y una string que representa la secuencia de operaciones para llegar a N’ desde N .
- Inicialmente, agregue un estado {N, «»} que represente N y la secuencia de operaciones como vacío en la cola.
- Agregue un estado {1, «/»} para la operación de división en la cola también.
- Durante el recorrido primero en amplitud , para cada estado, agregue dos estados donde el primer estado representará la suma (N’ + N’) y el segundo estado representará la multiplicación (N’ * N’) .
- Mantenga un mapa desordenado para verificar si el estado actual ya se visitó durante el BFS Traversal .
- Si el valor del estado actual es igual a M , entonces la secuencia de operaciones obtenida hasta M es el resultado. De lo contrario, imprima «-1» .
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;
// Function to find the sequence of
// minimum number of operations needed
// to convert N into M using +, -, *, /
string changeNtoM(int N, int M)
{
// Case where N and M are same
if (N == M) {
return " ";
}
// Case where M = 0
if (M == 0) {
return "-";
}
// Stores the BFS states in a queue
queue<pair<int, string> > q;
// Stores if current state is visited
unordered_map<int, bool> visited;
// Initial State
q.push({ N, "" }), visited[N] = 1;
// State where the first operation is /
q.push({ 1, "/" }), visited[1] = 1;
// Loop for the BFS traversal
while (!q.empty()) {
// Stores the current BFS state
pair<int, string> cur = q.front();
q.pop();
// If the value of current state is
// equal to M return the stored
// sequence of operations
if (cur.first == M) {
// Return answer
return cur.second;
}
// Adding 1st state representing the
// addition operation(N' + N')
if (!visited[cur.first + cur.first]
&& cur.first + cur.first <= M) {
// Add state into queue and
// mark the state visited
q.push({ cur.first + cur.first,
cur.second + "+" });
visited[cur.first + cur.first] = 1;
}
// Adding 2nd state representing the
// multiplication operation(N' * N')
if (!visited[cur.first * cur.first]
&& cur.first * cur.first <= M) {
// Add state into queue and
// mark the state visited
q.push({ cur.first * cur.first,
cur.second + "*" });
visited[cur.first * cur.first] = 1;
}
}
// No valid sequence of operations exist
return "-1";
}
// Driver Code
int main()
{
int N = 7, M = 392;
string result = changeNtoM(N, M);
if (result == "-1")
cout << result << endl;
else
cout << result.length() << endl
<< result;
return 0;
}
Javascript
// JavaScript program for the above approach
// Function to find the sequence of
// minimum number of operations needed
// to convert N into M using +, -, *, /
function changeNtoM(N, M)
{
// Case where N and M are same
if (N == M) {
return " ";
}
// Case where M = 0
if (M == 0) {
return "-";
}
// Stores the BFS states in a queue
let q = [];
// Stores if current state is visited
let visited = new Map();
// Initial State
q.push([N, "" ]);
visited.set(N, 1);
// State where the first operation is /
q.push([1, "/"]);
visited.set(1, 1);
// Loop for the BFS traversal
while (q.length > 0) {
// Stores the current BFS state
let cur = q.shift();
// If the value of current state is
// equal to M return the stored
// sequence of operations
if (cur[0] == M) {
// Return answer
return cur[1];
}
// Adding 1st state representing the
// addition operation(N' + N')
if (!visited.has((2*cur[0])) && 2*cur[0]<= M) {
// Add state into queue and
// mark the state visited
q.push([2*cur[0], cur[1] + "+"]);
visited.set((cur[0] + cur[0]), 1);
}
// Adding 2nd state representing the
// multiplication operation(N' * N')
if (!visited.has((cur[0]* cur[0])) && cur[0] * cur[0] <= M) {
// Add state into queue and
// mark the state visited
q.push([cur[0] * cur[0], cur[1] + "*" ]);
visited.set((cur[0]* cur[0]), 1);
}
}
// No valid sequence of operations exist
return "-1";
}
// Driver Code
let N = 7;
let M = 392;
let result = changeNtoM(N, M);
if (result == "-1")
console.log(result);
else{
console.log(result.length);
console.log(result);
}
// The code is contributed by Nidhi goel
Producción:
3 +*+
Complejidad de tiempo: O(min(2 log 2 (M – N) , M – N))
Espacio auxiliar: O((MN)* log 2 (M – N))
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA