Dados dos números enteros N y M , la tarea es encontrar el menor número de operaciones necesarias para convertir N en M . Cada operación implica sumar uno de los factores primos del valor actual de N . Si es posible obtener M, imprima el número de operaciones. De lo contrario, imprima -1 .
Ejemplos:
Entrada: N = 6, M = 10
Salida: 2
Explicación:
Los factores primos de 6 son [2, 3].
Sumando 2 a N, obtenemos 8.
El factor primo de 8 es [2].
Sumando 2 a N, obtenemos 10, que es el resultado deseado.
Por lo tanto, pasos totales = 2Entrada: N = 2, M = 3
Salida: -1
Explicación:
No hay forma de convertir N = 2 a M = 3.
Enfoque:
el problema se puede resolver utilizando BFS para obtener los pasos mínimos para llegar a M y la criba de Eratóstenes para calcular previamente los números primos.
Siga los pasos a continuación para resolver el problema:
- Almacene y calcule previamente todos los números primos usando Sieve.
- Ahora, si N ya es igual a M, imprima 0 ya que no se requiere ninguna operación de suma.
- Visualice este problema como un problema gráfico para realizar BFS . En cada nivel, almacene los números alcanzables de los valores de N en el nivel anterior agregando factores primos.
- Ahora, comience insertando (N, 0) , donde N denota el valor y 0 denota el número de operaciones para alcanzar ese valor, en la cola inicialmente.
- En cada nivel de la cola, recorra todos los elementos uno por uno extrayendo el elemento en el frente() y realice lo siguiente:
- Almacene q.front().first() en newNum y q.front().second() en distance , donde newNum es el valor actual y distancia es el número de operaciones necesarias para alcanzar este valor.
- Almacene todos los factores primos de newNum en un conjunto .
- Si newNum es igual a M , entonces imprima la distancia, ya que son las operaciones mínimas requeridas.
- Si newNum es mayor que M, entonces se rompe.
- De lo contrario, newNum es menor que M. Entonces, actualice newNum agregando sus factores primos i uno por uno y almacene (newNum + i, distancia + 1) en la cola y repita los pasos anteriores para el siguiente nivel.
- Si la búsqueda continúa hasta un nivel en el que la cola se vacía, significa que M no se puede obtener de N. Imprimir -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum // steps required to convert a number // N to M. #include <bits/stdc++.h> using namespace std; // Array to store shortest prime // factor of every integer int spf[100009]; // Function to precompute // shortest prime factors void sieve() { memset(spf, -1, 100005); for (int i = 2; i * i <= 100005; i++) { for (int j = i; j <= 100005; j += i) { if (spf[j] == -1) { spf[j] = i; } } } } // Function to insert distinct prime factors // of every integer into a set set<int> findPrimeFactors(set<int> s, int n) { // Store distinct prime // factors while (n > 1) { s.insert(spf[n]); n /= spf[n]; } return s; } // Function to return minimum // steps using BFS int MinimumSteps(int n, int m) { // Queue of pairs to store // the current number and // distance from root. queue<pair<int, int> > q; // Set to store distinct // prime factors set<int> s; // Run BFS q.push({ n, 0 }); while (!q.empty()) { int newNum = q.front().first; int distance = q.front().second; q.pop(); // Find out the prime factors of newNum set<int> k = findPrimeFactors(s, newNum); // Iterate over every prime // factor of newNum. for (auto i : k) { // If M is obtained if (newNum == m) { // Return number of // operations return distance; } // If M is exceeded else if (newNum > m) { break; } // Otherwise else { // Update and store the new // number obtained by prime factor q.push({ newNum + i, distance + 1 }); } } } // If M cannot be obtained return -1; } // Driver code int main() { int N = 7, M = 16; sieve(); cout << MinimumSteps(N, M); }
Java
// Java program to find the minimum // steps required to convert a number // N to M. import java.util.*; class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Array to store shortest prime // factor of every integer static int []spf = new int[100009]; // Function to precompute // shortest prime factors static void sieve() { for(int i = 0; i < 100005; i++) spf[i] = -1; for(int i = 2; i * i <= 100005; i++) { for(int j = i; j <= 100005; j += i) { if (spf[j] == -1) { spf[j] = i; } } } } // Function to insert distinct prime factors // of every integer into a set static HashSet<Integer> findPrimeFactors(HashSet<Integer> s, int n) { // Store distinct prime // factors while (n > 1) { s.add(spf[n]); n /= spf[n]; } return s; } // Function to return minimum // steps using BFS static int MinimumSteps(int n, int m) { // Queue of pairs to store // the current number and // distance from root. Queue<pair > q = new LinkedList<>(); // Set to store distinct // prime factors HashSet<Integer> s = new HashSet<Integer>(); // Run BFS q.add(new pair(n, 0)); while (!q.isEmpty()) { int newNum = q.peek().first; int distance = q.peek().second; q.remove(); // Find out the prime factors of newNum HashSet<Integer> k = findPrimeFactors(s, newNum); // Iterate over every prime // factor of newNum. for(int i : k) { // If M is obtained if (newNum == m) { // Return number of // operations return distance; } // If M is exceeded else if (newNum > m) { break; } // Otherwise else { // Update and store the new // number obtained by prime factor q.add(new pair(newNum + i, distance + 1 )); } } } // If M cannot be obtained return -1; } // Driver code public static void main(String[] args) { int N = 7, M = 16; sieve(); System.out.print(MinimumSteps(N, M)); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program to find the minimum # steps required to convert a number # N to M. # Array to store shortest prime # factor of every integer spf = [-1 for i in range(100009)]; # Function to precompute # shortest prime factors def sieve(): i=2 while(i * i <= 100006): for j in range(i, 100006, i): if (spf[j] == -1): spf[j] = i; i += 1 # Function to append distinct prime factors # of every integer into a set def findPrimeFactors(s, n): # Store distinct prime # factors while (n > 1): s.add(spf[n]); n //= spf[n]; return s; # Function to return minimum # steps using BFS def MinimumSteps( n, m): # Queue of pairs to store # the current number and # distance from root. q = [] # Set to store distinct # prime factors s = set() # Run BFS q.append([ n, 0 ]) while (len(q) != 0): newNum = q[0][0] distance = q[0][1] q.pop(0); # Find out the prime factors of newNum k = findPrimeFactors(s, newNum); # Iterate over every prime # factor of newNum. for i in k: # If M is obtained if (newNum == m): # Return number of # operations return distance; # If M is exceeded elif (newNum > m): break; # Otherwise else: # Update and store the new # number obtained by prime factor q.append([ newNum + i, distance + 1 ]); # If M cannot be obtained return -1; # Driver code if __name__=='__main__': N = 7 M = 16; sieve(); print( MinimumSteps(N, M)) # This code is contributed by rutvik_56
C#
// C# program to find the minimum // steps required to convert a number // N to M. using System; using System.Collections.Generic; class GFG{ class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Array to store shortest prime // factor of every integer static int []spf = new int[100009]; // Function to precompute // shortest prime factors static void sieve() { for(int i = 0; i < 100005; i++) spf[i] = -1; for(int i = 2; i * i <= 100005; i++) { for(int j = i; j <= 100005; j += i) { if (spf[j] == -1) { spf[j] = i; } } } } // Function to insert distinct prime factors // of every integer into a set static HashSet<int> findPrimeFactors(HashSet<int> s, int n) { // Store distinct prime // factors while (n > 1) { s.Add(spf[n]); n /= spf[n]; } return s; } // Function to return minimum // steps using BFS static int MinimumSteps(int n, int m) { // Queue of pairs to store // the current number and // distance from root. Queue<pair> q = new Queue<pair>(); // Set to store distinct // prime factors HashSet<int> s = new HashSet<int>(); // Run BFS q.Enqueue(new pair(n, 0)); while (q.Count != 0) { int newNum = q.Peek().first; int distance = q.Peek().second; q.Dequeue(); // Find out the prime factors of newNum HashSet<int> k = findPrimeFactors(s, newNum); // Iterate over every prime // factor of newNum. foreach(int i in k) { // If M is obtained if (newNum == m) { // Return number of // operations return distance; } // If M is exceeded else if (newNum > m) { break; } // Otherwise else { // Update and store the new // number obtained by prime factor q.Enqueue(new pair(newNum + i, distance + 1)); } } } // If M cannot be obtained return -1; } // Driver code public static void Main(String[] args) { int N = 7, M = 16; sieve(); Console.Write(MinimumSteps(N, M)); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript program to find the minimum // steps required to convert a number // N to M. class pair { constructor(first, second) { this.first = first; this.second = second; } } // Array to store shortest prime // factor of every integer var spf = Array(100009).fill(0); // Function to precompute // shortest prime factors function sieve() { for(var i = 0; i < 100005; i++) spf[i] = -1; for(var i = 2; i * i <= 100005; i++) { for(var j = i; j <= 100005; j += i) { if (spf[j] == -1) { spf[j] = i; } } } } // Function to insert distinct prime factors // of every integer into a set function findPrimeFactors(s, n) { // Store distinct prime // factors while (n > 1) { s.add(spf[n]); n /= spf[n]; } return s; } // Function to return minimum // steps using BFS function MinimumSteps(n, m) { // Queue of pairs to store // the current number and // distance from root. var q = []; // Set to store distinct // prime factors var s = new Set(); // Run BFS q.push(new pair(n, 0)); while (q.length != 0) { var newNum = q[0].first; var distance = q[0].second; q.shift(); // Find out the prime factors of newNum var k = findPrimeFactors(s, newNum); // Iterate over every prime // factor of newNum. for(var i of k) { // If M is obtained if (newNum == m) { // Return number of // operations return distance; } // If M is exceeded else if (newNum > m) { break; } // Otherwise else { // Update and store the new // number obtained by prime factor q.push(new pair(newNum + i, distance + 1)); } } } // If M cannot be obtained return -1; } // Driver code var N = 7, M = 16; sieve(); document.write(MinimumSteps(N, M)); </script>
2
Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA