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>
Producción:
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