Paso mínimo para llegar a uno

Dado un número positivo N, necesitamos llegar a 1 en un número mínimo de pasos donde un paso se define como convertir N en (N-1) o convertir N en uno de los divisores más grandes. 

Formalmente, si estamos en N, entonces en 1 paso podemos llegar a (N – 1) o si N = u*v entonces podemos llegar a max(u, v) donde u > 1 y v > 1. 

Ejemplos:

Input : N = 17
Output : 4
We can reach to 1 in 4 steps as shown below,
17 -> 16(from 17 - 1) -> 4(from 4 * 4) -> 
2(from 2 * 2) -> 1(from 2 - 1)

Input : N = 50
Output : 5
We can reach to 1 in 5 steps as shown below,
50 -> 10(from 5 * 10) -> 5(from 2 * 5) -> 
4(from 5 - 1) -> 2(from 2 *2) -> 1(from 2 - 1)

Podemos resolver este problema utilizando la búsqueda primero en amplitud porque funciona nivel por nivel, por lo que llegaremos a 1 en un número mínimo de pasos donde el siguiente nivel para N contiene (N – 1) y factores propios más grandes de N. 
El procedimiento BFS completo será como A continuación, primero empujaremos N con los pasos 0 en la cola de datos y luego, en cada nivel, empujaremos los elementos del siguiente nivel con 1 paso más que los elementos del nivel anterior. De esta manera, cuando 1 salga de la cola, contendrá una cantidad mínima de pasos, que será nuestro resultado final. 
En el código a continuación, se usa una cola de una estructura de tipo ‘datos’ que almacena valor y pasos desde N en él, se usa otro conjunto de tipo entero para evitar presionar el mismo elemento más de una vez, lo que puede conducir a un ciclo infinito . Entonces, en cada paso, colocamos el valor en el conjunto después de colocarlo en la cola para que el valor no se visite más de una vez. 

Consulte el código a continuación para una mejor comprensión,  

C++

//  C++ program to get minimum step to reach 1
// under given constraints
#include <bits/stdc++.h>
using namespace std;
 
//  structure represent one node in queue
struct data
{
    int val;
    int steps;
    data(int val, int steps) : val(val), steps(steps)
    {}
};
 
//  method returns minimum step to reach one
int minStepToReachOne(int N)
{
    queue<data> q;
    q.push(data(N, 0));
 
    // set is used to visit numbers so that they
    // won't be pushed in queue again
    set<int> st;
 
    //  loop until we reach to 1
    while (!q.empty())
    {
        data t = q.front();     q.pop();
         
        // if current data value is 1, return its
        // steps from N
        if (t.val == 1)
            return t.steps;
 
        //  check curr - 1, only if it not visited yet
        if (st.find(t.val - 1) == st.end())
        {
            q.push(data(t.val - 1, t.steps + 1));
            st.insert(t.val - 1);
        }
 
        //  loop from 2 to sqrt(value) for its divisors
        for (int i = 2; i*i <= t.val; i++)
        {
 
            // check divisor, only if it is not visited yet
            // if i is divisor of val, then val / i will
            // be its bigger divisor
            if (t.val % i == 0 && st.find(t.val / i) == st.end())
            {
                q.push(data(t.val / i, t.steps + 1));
                st.insert(t.val / i);
            }
        }
    }
}
 
//  Driver code to test above methods
int main()
{
    int N = 17;
    cout << minStepToReachOne(N) << endl;
}

Java

// Java program to get minimum step to reach 1
// under given constraints
import java.util.*;
 
class GFG
{
 
// structure represent one node in queue
static class data
{
    int val;
    int steps;
    public data(int val, int steps)
    {
        this.val = val;
        this.steps = steps;
    }
     
};
 
// method returns minimum step to reach one
static int minStepToReachOne(int N)
{
    Queue<data> q = new LinkedList<>();
    q.add(new data(N, 0));
 
    // set is used to visit numbers so that they
    // won't be pushed in queue again
    HashSet<Integer> st = new HashSet<Integer>();
 
    // loop until we reach to 1
    while (!q.isEmpty())
    {
        data t = q.peek(); q.remove();
         
        // if current data value is 1, return its
        // steps from N
        if (t.val == 1)
            return t.steps;
 
        // check curr - 1, only if it not visited yet
        if (!st.contains(t.val - 1))
        {
            q.add(new data(t.val - 1, t.steps + 1));
            st.add(t.val - 1);
        }
 
        // loop from 2 to Math.sqrt(value) for its divisors
        for (int i = 2; i*i <= t.val; i++)
        {
 
            // check divisor, only if it is not visited yet
            // if i is divisor of val, then val / i will
            // be its bigger divisor
            if (t.val % i == 0 && !st.contains(t.val / i) )
            {
                q.add(new data(t.val / i, t.steps + 1));
                st.add(t.val / i);
            }
        }
    }
    return -1;
}
 
// Driver code 
public static void main(String[] args)
{
    int N = 17;
    System.out.print(minStepToReachOne(N) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to get minimum step
# to reach 1 under given constraints
 
# Structure represent one node in queue
class data:
 
    def __init__(self, val, steps):
        self.val = val
        self.steps = steps
 
 
# Method returns minimum step to reach one
def minStepToReachOne(N):
    q = []
    q.append(data(N, 0))
 
    # Set is used to visit numbers
    # so that they won't be pushed
    # in queue again
    st = set()
 
    # Loop until we reach to 1
    while (len(q)):
 
        t = q.pop(0)
 
        # If current data value is 1,
        # return its steps from N
        if (t.val == 1):
            return t.steps
 
        # Check curr - 1, only if
        # it not visited yet
        if not (t.val - 1) in st:
            q.append(data(t.val - 1, t.steps + 1))
            st.add(t.val - 1)
 
        # Loop from 2 to Math.sqrt(value)
        # for its divisors
        for i in range(2, int((t.val) ** 0.5) + 1):
 
            # Check divisor, only if it is not
            # visited yet if i is divisor of val,
            # then val / i will be its bigger divisor
            if (t.val % i == 0 and (t.val / i) not in st):
                q.append(data(t.val / i, t.steps + 1))
                st.add(t.val / i)
    return -1
 
# Driver code
N = 17
print(minStepToReachOne(N))
 
# This code is contributed by phasing17

C#

// C# program to get minimum step to reach 1
// under given constraints
using System;
using System.Collections.Generic;
 
class GFG
{
 
// structure represent one node in queue
class data
{
    public int val;
    public int steps;
    public data(int val, int steps)
    {
        this.val = val;
        this.steps = steps;
    }
};
 
// method returns minimum step to reach one
static int minStepToReachOne(int N)
{
    Queue<data> q = new Queue<data>();
    q.Enqueue(new data(N, 0));
 
    // set is used to visit numbers so that they
    // won't be pushed in queue again
    HashSet<int> st = new HashSet<int>();
 
    // loop until we reach to 1
    while (q.Count != 0)
    {
        data t = q.Peek(); q.Dequeue();
         
        // if current data value is 1, return its
        // steps from N
        if (t.val == 1)
            return t.steps;
 
        // check curr - 1, only if it not visited yet
        if (!st.Contains(t.val - 1))
        {
            q.Enqueue(new data(t.val - 1, t.steps + 1));
            st.Add(t.val - 1);
        }
 
        // loop from 2 to Math.Sqrt(value) for its divisors
        for (int i = 2; i*i <= t.val; i++)
        {
 
            // check divisor, only if it is not visited yet
            // if i is divisor of val, then val / i will
            // be its bigger divisor
            if (t.val % i == 0 && !st.Contains(t.val / i) )
            {
                q.Enqueue(new data(t.val / i, t.steps + 1));
                st.Add(t.val / i);
            }
        }
    }
    return -1;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 17;
    Console.Write(minStepToReachOne(N) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to get minimum step
// to reach 1 under given constraints
 
// Structure represent one node in queue
class data
{
    constructor(val, steps)
    {
        this.val = val;
        this.steps = steps;
    }
}
 
// Method returns minimum step to reach one
function minStepToReachOne(N)
{
    let q = [];
    q.push(new data(N, 0));
   
    // Set is used to visit numbers
    // so that they won't be pushed
    // in queue again
    let st = new Set();
   
    // Loop until we reach to 1
    while (q.length != 0)
    {
        let t = q.shift();
           
        // If current data value is 1,
        // return its steps from N
        if (t.val == 1)
            return t.steps;
   
        // Check curr - 1, only if
        // it not visited yet
        if (!st.has(t.val - 1))
        {
            q.push(new data(t.val - 1,
                          t.steps + 1));
            st.add(t.val - 1);
        }
   
        // Loop from 2 to Math.sqrt(value)
        // for its divisors
        for(let i = 2; i*i <= t.val; i++)
        {
             
            // Check divisor, only if it is not
            // visited yet if i is divisor of val,
            // then val / i will be its bigger divisor
            if (t.val % i == 0 && !st.has(t.val / i))
            {
                q.push(new data(t.val / i,
                              t.steps + 1));
                st.add(t.val / i);
            }
        }
    }
    return -1;
}
 
// Driver code 
let N = 17;
document.write(minStepToReachOne(N) + "<br>");
 
// This code is contributed by rag2127
 
</script>

Producción: 

4

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *