Dados dos números N y M, la tarea es encontrar el número mínimo de movimientos para cambiar N a M o -1 si es imposible. En un movimiento, agregue al número actual cualquiera de sus divisores que no sean 1 y el número en sí.
Ejemplos:
Entrada: N = 4, M = 24
Salida: 5
Explicación: el número 24 se puede llegar a partir de 4 mediante 5 operaciones: 4->6->8->12->18->24.Entrada: N = 4, M = 576
Salida: 14
Enfoque: construya un gráfico donde los vértices sean números de N a M y haya una arista desde el vértice v1 hasta el vértice v2 si se puede obtener v2 de v1 usando exactamente una operación del enunciado del problema. Para resolver el problema, encuentra el camino más corto desde el vértice N hasta el vértice M en este gráfico. Esto se puede hacer usando el algoritmo de búsqueda primero en amplitud . Siga los pasos a continuación para resolver el problema:
- Inicialice una array booleana visitada [] para almacenar si un número en particular se cuenta o no.
- Rellene todos los índices de la array booleana visited[] con el valor falso y establezca el valor de visited[N] en verdadero.
- Inicialice una cola de pares q para almacenar el número visitado y el número de operaciones realizadas.
- Empuje el par {N, 0} a la cola de pares q .
- Iterar en un rango hasta que la cola de pares q no esté vacía .
- Inicialice las variables aux como el primer valor del par frontal de la cola q y cont como el segundo valor del par frontal de la cola q.
- Saque el par delantero de la cola de pares q.
- Si aux es igual a M, entonces devuelve el valor de cont.
- Iterar en un rango [2, aux 1/2 ] y realizar los siguientes pasos.
- Si i es un factor de aux, siga los siguientes pasos.
- Si aux+i es menor que M y visited[i+aux] es falso, establezca el valor de visited[aux+i] en verdadero y coloque el par {aux+i, cont+1} en la cola de parejas q.
- Si aux+aux/i es menor que M y visited[aux/i+aux] es falso, establezca el valor de visited[aux+aux/i] en verdadero y empuje el par {aux+aux/i, cont+1} en la cola de pares q.
- Si i es un factor de aux, siga los siguientes pasos.
- Devuelve -1 ya que es imposible hacer que N sea igual a M.
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 minimum number
// of moves to make N and M equal.
int countOperations(int N, int M)
{
// Array to maintain the numbers
// included.
bool visited[100001];
fill(visited, visited + 100001, false);
// pair of vertex, count
queue<pair<int, int> > Q;
Q.push(make_pair(N, 0));
visited[N] = true;
// run bfs from N
while (!Q.empty()) {
int aux = Q.front().first;
int cont = Q.front().second;
Q.pop();
// if we reached goal
if (aux == M)
return cont;
// Iterate in the range
for (int i = 2; i * i <= aux; i++)
// If i is a factor of aux
if (aux % i == 0) {
// If i is less than M-aux and
// is not included earlier.
if (aux + i <= M && !visited[aux + i]) {
Q.push(make_pair(aux + i, cont + 1));
visited[aux + i] = true;
}
// If aux/i is less than M-aux and
// is not included earlier.
if (aux + aux / i <= M
&& !visited[aux + aux / i]) {
Q.push(
make_pair(aux + aux / i, cont + 1));
visited[aux + aux / i] = true;
}
}
}
// Not possible
return -1;
}
// Driver Code
int main()
{
int N = 4, M = 24;
cout << countOperations(N, M);
return 0;
}
Java
// Java program for above approach
import java.util.*;
class GFG{
static class pair<T, V>
{
T first;
V second;
}
static pair<Integer, Integer> make_pair(int f, int s)
{
pair<Integer, Integer> p = new pair<>();
p.first = f; p.second = s;
return p;
}
// Function to find the minimum number
// of moves to make N and M equal.
static int countOperations(int N, int M)
{
// Array to maintain the numbers
// included.
boolean[] visited = new boolean[100001];
Arrays.fill(visited, false);
// Pair of vertex, count
Queue<pair<Integer, Integer>> Q = new LinkedList<>();
Q.add(make_pair(N, 0));
visited[N] = true;
// Run bfs from N
while (!Q.isEmpty())
{
int aux = Q.peek().first;
int cont = Q.peek().second;
Q.remove();
// If we reached goal
if (aux == M)
return cont;
// Iterate in the range
for(int i = 2; i * i <= aux; i++)
// If i is a factor of aux
if (aux % i == 0)
{
// If i is less than M-aux and
// is not included earlier.
if (aux + i <= M && !visited[aux + i])
{
Q.add(make_pair(aux + i, cont + 1));
visited[aux + i] = true;
}
// If aux/i is less than M-aux and
// is not included earlier.
if (aux + aux / i <= M &&
!visited[aux + aux / i])
{
Q.add(make_pair(aux + aux / i,
cont + 1));
visited[aux + aux / i] = true;
}
}
}
// Not possible
return -1;
}
// Driver Code
public static void main(String[] args)
{
int N = 4, M = 24;
System.out.println(countOperations(N, M));
}
}
// This code is contributed by hritikrommie
Python3
# Python3 program for the above approach. # Function to find the minimum number # of moves to make N and M equal. def countOperations(N, M): # Array to maintain the numbers # included. visited = [False] * (100001) # Pair of vertex, count Q = [] Q.append([N, 0]) visited[N] = True # Run bfs from N while (len(Q) > 0): aux = Q[0][0] cont = Q[0][1] Q.pop(0) # If we reached goal if (aux == M): return cont # Iterate in the range i = 2 while i * i <= aux: # If i is a factor of aux if (aux % i == 0): # If i is less than M-aux and # is not included earlier. if (aux + i <= M and not visited[aux + i]): Q.append([aux + i, cont + 1]) visited[aux + i] = True # If aux/i is less than M-aux and # is not included earlier. if (aux + int(aux / i) <= M and not visited[aux + int(aux / i)]): Q.append([aux + int(aux / i), cont + 1]) visited[aux + int(aux / i)] = True i += 1 # Not possible return -1 # Driver code N, M = 4, 24 print(countOperations(N, M)) # This code is contributed by mukesh07
C#
// C# program for the above approach.
using System;
using System.Collections;
class GFG
{
// Function to find the minimum number
// of moves to make N and M equal.
static int countOperations(int N, int M)
{
// Array to maintain the numbers
// included.
bool[] visited = new bool[100001];
// pair of vertex, count
Queue Q = new Queue();
Q.Enqueue(new Tuple<int, int>(N, 0));
visited[N] = true;
// run bfs from N
while (Q.Count > 0) {
int aux = ((Tuple<int,int>)(Q.Peek())).Item1;
int cont = ((Tuple<int,int>)(Q.Peek())).Item2;
Q.Dequeue();
// if we reached goal
if (aux == M)
return cont;
// Iterate in the range
for (int i = 2; i * i <= aux; i++)
// If i is a factor of aux
if (aux % i == 0)
{
// If i is less than M-aux and
// is not included earlier.
if (aux + i <= M && !visited[aux + i]) {
Q.Enqueue(new Tuple<int, int>(aux + i, cont + 1));
visited[aux + i] = true;
}
// If aux/i is less than M-aux and
// is not included earlier.
if (aux + aux / i <= M
&& !visited[aux + aux / i]) {
Q.Enqueue(new Tuple<int, int>(aux + aux / i, cont + 1));
visited[aux + aux / i] = true;
}
}
}
// Not possible
return -1;
}
static void Main ()
{
int N = 4, M = 24;
Console.WriteLine(countOperations(N, M));
}
}
// This code is contributed by suresh07.
Javascript
<script>
// Javascript program for the above approach.
// Function to find the minimum number
// of moves to make N and M equal.
function countOperations(N, M)
{
// Array to maintain the numbers
// included.
let visited = new Array(100001);
// pair of vertex, count
let Q = [];
Q.push([N, 0]);
visited[N] = true;
// run bfs from N
while (Q.length > 0) {
let aux = Q[0][0];
let cont = Q[0][1];
Q.shift();
// if we reached goal
if (aux == M)
return cont;
// Iterate in the range
for (let i = 2; i * i <= aux; i++)
// If i is a factor of aux
if (aux % i == 0)
{
// If i is less than M-aux and
// is not included earlier.
if (aux + i <= M && !visited[aux + i]) {
Q.push([aux + i, cont + 1]);
visited[aux + i] = true;
}
// If aux/i is less than M-aux and
// is not included earlier.
if (aux + parseInt(aux / i, 10) <= M
&& !visited[aux + parseInt(aux / i, 10)]) {
Q.push([aux + parseInt(aux / i, 10), cont + 1]);
visited[aux + parseInt(aux / i, 10)] = true;
}
}
}
// Not possible
return -1;
}
let N = 4, M = 24;
document.write(countOperations(N, M));
// This code is contributed by rameshtravel07.
</script>
Producción
5
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA