Dado un número N y algunas operaciones que se pueden realizar, la tarea es encontrar el número mínimo de movimientos para convertir N en 0. En una operación de movimiento, se puede realizar una de las siguientes:
- Incrementa o decrementa el valor de N en 1.
- Multiplica el valor de N por -1.
- Divide el valor de N por 2 si N es par.
- Reducir el valor de N a √N si N es un cuadrado perfecto.
Ejemplo:
Entrada: N = 50
Salida: 6
Explicación: Los movimientos realizados son: 50 (/2) -> 25 (√) -> 5 (- 1) -> 4 (/2) -> 2 (-1) -> 1 (-1) -> 0. Por lo tanto, el número requerido de movimientos es 6, que es el mínimo posible.Entrada: N = 75
Salida: 8
Enfoque: el problema dado se puede resolver de manera eficiente mediante el uso de programación dinámica. La idea es utilizar hashing y búsqueda en amplitud en 0 hasta que se alcance N. Se utiliza hash para que el mismo número no sea visitado dos veces. Se pueden seguir los siguientes pasos para resolver el problema:
- Use BFS agregando todos los números posibles que se pueden alcanzar desde 0 en una cola y también en un hashmap para que no se vuelvan a visitar
- Devuelve el número de movimientos calculados después de llegar a N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val, moves;
// Constructor
Node(int v, int m)
{
val = v;
moves = m;
}
};
// Function to calculate
// minimum number of moves
// required to convert N to 0
int minMoves(int N)
{
// Initialize a hashset
// to mark the visited numbers
set<int> set;
// Initialize a queue
queue<Node*> q ;
// Mark 0 as visited
set.insert(0);
// Add 0 into the queue
q.push(new Node(0, 0));
// while N is not reached
while (!q.empty()) {
// poll out current node
Node *curr = q.front();
q.pop();
// If N is reached
if (curr->val == N) {
// Return the number of moves used
return curr->moves;
}
if (set.find(curr->val - 1)==set.end()) {
// Mark the number as visited
set.insert(curr->val - 1);
// Add the number in the queue
q.push(new Node(curr->val - 1,
curr->moves + 1));
}
if (set.find(curr->val + 1)==set.end()) {
// Mark the number as visited
set.insert(curr->val + 1);
// Add the number in the queue
q.push(new Node(curr->val + 1,
curr->moves + 1));
}
if (set.find(curr->val * 2)==set.end()) {
// Mark the number as visited
set.insert(curr->val * 2);
// Add the number in the queue
q.push(new Node(curr->val * 2,
curr->moves + 1));
}
int sqr = curr->val * curr->val;
if (set.find(sqr)==set.end()) {
// Mark the number as visited
set.insert(sqr);
// Add the number in the queue
q.push(new Node(sqr,
curr->moves + 1));
}
if (set.find(-curr->val)==set.end()) {
// Mark the number as visited
set.insert(-curr->val);
// Add the number in the queue
q.push(new Node(-curr->val,
curr->moves + 1));
}
}
return -1;
}
// Driver code
int main()
{
int N = 50;
// Call the function
// and print the answer
cout<<(minMoves(N));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
static class Node {
int val, moves;
// Constructor
public Node(int val, int moves)
{
this.val = val;
this.moves = moves;
}
}
// Function to calculate
// minimum number of moves
// required to convert N to 0
public static int minMoves(int N)
{
// Initialize a hashset
// to mark the visited numbers
Set<Integer> set = new HashSet<>();
// Initialize a queue
Queue<Node> q = new LinkedList<>();
// Mark 0 as visited
set.add(0);
// Add 0 into the queue
q.add(new Node(0, 0));
// while N is not reached
while (!q.isEmpty()) {
// poll out current node
Node curr = q.poll();
// If N is reached
if (curr.val == N) {
// Return the number of moves used
return curr.moves;
}
if (!set.contains(curr.val - 1)) {
// Mark the number as visited
set.add(curr.val - 1);
// Add the number in the queue
q.add(new Node(curr.val - 1,
curr.moves + 1));
}
if (!set.contains(curr.val + 1)) {
// Mark the number as visited
set.add(curr.val + 1);
// Add the number in the queue
q.add(new Node(curr.val + 1,
curr.moves + 1));
}
if (!set.contains(curr.val * 2)) {
// Mark the number as visited
set.add(curr.val * 2);
// Add the number in the queue
q.add(new Node(curr.val * 2,
curr.moves + 1));
}
int sqr = curr.val * curr.val;
if (!set.contains(sqr)) {
// Mark the number as visited
set.add(sqr);
// Add the number in the queue
q.add(new Node(sqr,
curr.moves + 1));
}
if (!set.contains(-curr.val)) {
// Mark the number as visited
set.add(-curr.val);
// Add the number in the queue
q.add(new Node(-curr.val,
curr.moves + 1));
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int N = 50;
// Call the function
// and print the answer
System.out.println(minMoves(N));
}
}
Python3
# Python code for the above approach from queue import Queue class Node: # Constructor def __init__(self, v, m): self.val = v self.moves = m # Function to calculate # minimum number of moves # required to convert N to 0 def minMoves(N): # Initialize a hashset # to mark the visited numbers _set = set() # Initialize a queue q = Queue() # Mark 0 as visited _set.add(0) # Add 0 into the queue q.put(Node(0, 0)) # while N is not reached while (q.qsize): # poll out current node curr = q.queue[0] q.get() # If N is reached if (curr.val == N): # Return the number of moves used return curr.moves if (not (curr.val - 1) in _set): # Mark the number as visited _set.add(curr.val - 1) # Add the number in the queue q.put(Node(curr.val - 1, curr.moves + 1)) if (not (curr.val + 1) in _set): # Mark the number as visited _set.add(curr.val + 1) # Add the number in the queue q.put(Node(curr.val + 1, curr.moves + 1)) if (not (curr.val * 2) in _set): # Mark the number as visited _set.add(curr.val * 2) # Add the number in the queue q.put(Node(curr.val * 2, curr.moves + 1)) sqr = curr.val * curr.val if (not sqr in _set): # Mark the number as visited _set.add(sqr) # Add the number in the queue q.put(Node(sqr, curr.moves + 1)) if (not (-curr.val) in _set): # Mark the number as visited _set.add(-curr.val) # Add the number in the queue q.put(Node(-curr.val, curr.moves + 1)) return -1 # Driver code N = 50 # Call the function # and print the answer print((minMoves(N))) # This code is contributed by gfgking
Javascript
<script>
// Javascript code for the above approach
class Node {
// Constructor
constructor(v, m) {
this.val = v;
this.moves = m;
}
};
// Function to calculate
// minimum number of moves
// required to convert N to 0
function minMoves(N) {
// Initialize a hashset
// to mark the visited numbers
let set = new Set();
// Initialize a queue
let q = [];
// Mark 0 as visited
set.add(0);
// Add 0 into the queue
q.unshift(new Node(0, 0));
// while N is not reached
while (q.length) {
// poll out current node
let curr = q[q.length - 1];
q.pop();
// If N is reached
if (curr.val == N) {
// Return the number of moves used
return curr.moves;
}
if (!set.has(curr.val - 1)) {
// Mark the number as visited
set.add(curr.val - 1);
// Add the number in the queue
q.unshift(new Node(curr.val - 1,
curr.moves + 1));
}
if (!set.has(curr.val + 1)) {
// Mark the number as visited
set.add(curr.val + 1);
// Add the number in the queue
q.unshift(new Node(curr.val + 1,
curr.moves + 1));
}
if (!set.has(curr.val * 2)) {
// Mark the number as visited
set.add(curr.val * 2);
// Add the number in the queue
q.unshift(new Node(curr.val * 2,
curr.moves + 1));
}
let sqr = curr.val * curr.val;
if (!set.has(sqr)) {
// Mark the number as visited
set.add(sqr);
// Add the number in the queue
q.unshift(new Node(sqr,
curr.moves + 1));
}
if (!set.has(-curr.val)) {
// Mark the number as visited
set.add(-curr.val);
// Add the number in the queue
q.unshift(new Node(-curr.val,
curr.moves + 1));
}
}
return -1;
}
// Driver code
let N = 50;
// Call the function
// and print the answer
document.write((minMoves(N)));
// This code is contributed by gfgking
</script>
Producción
6
Complejidad Temporal: O(log N)
Espacio Auxiliar: O(K*log N), donde K son las posibles operaciones permitidas
Publicación traducida automáticamente
Artículo escrito por rahul mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA