Dado un número entero N , la tarea es encontrar el número mínimo de pasos requeridos para cambiar el número N a una potencia perfecta de 2 usando los siguientes pasos:
- Elimine cualquier dígito d del número.
- Agrega cualquier dígito d al final del número N .
Ejemplos:
Entrada: N = 1092
Salida: 2
Explicación:
A continuación se detallan los pasos seguidos:
- Quitando el dígito 9 del número N(= 1092) lo modifica a 102.
- Agregar el dígito 4 al final del número N (= 102) lo modifica a 1024.
Después de las operaciones anteriores, el número N se convierte en potencia perfecta de 2 y el número de movimientos necesarios es 2, que es el mínimo. Por lo tanto, imprime 2.
Entrada: N = 4444
Salida: 3
Enfoque: El problema dado se puede resolver usando el Enfoque Greedy , la idea es almacenar todos los números que son la potencia de 2 y son menores que 10 20 y verificar con cada número los pasos mínimos para convertir el número dado en una potencia de 2. Siga los pasos a continuación para resolver el problema:
- Inicialice una array y almacene todos los números que son la potencia de 2 y menos que 10 20 .
- Inicialice la variable de respuesta mejor como longitud + 1 como el número máximo de pasos necesarios.
- Itere sobre el rango [0, len) donde len es la longitud de la array usando la variable x y realice los siguientes pasos:
- Inicialice la variable, digamos posición como 0 .
- Itere sobre el rango [0, len) donde len es la longitud del número usando la variable i y si la posición es menor que len(x) y x[position] es igual a num[i] , entonces aumente el valor de una posición por 1 .
- Actualice el valor de best como el mínimo de best o len(x) + len(num) – 2*position .
- Después de realizar los pasos anteriores, imprima el valor de mejor como resultado.
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
// steps required to reduce N to perfect
// power of 2 by performing given steps
void findMinimumSteps(int N){
string num = to_string(N);
long long c = 1;
stack<string>a;
// Stores all the perfect power of 2
while(true){
if (c > pow(10,20) || c>10)
break;
a.push(to_string(c));
c = c * 2;
}
// Maximum number of steps required
long long best = num.length() + 1;
// Iterate for each perfect power of 2
while(a.empty() == false){
string x = a.top();
a.pop();
long long position = 0;
// Comparing with all numbers
for(int i=0;i<num.length();i++){
if(position < x.length() && x[position] == num[i])
position += 1;
}
// Update the minimum number of
// steps required
best = min(best, (int)x.length() + (int)num.length() - 2 * position);
}
// Print the result
cout<<(best-1)<<endl;
}
// Driver Code
int main()
{
int N = 1092;
// Function Call
findMinimumSteps(N);
}
// code is contributed by shinjanpatra
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG {
// Function to find the minimum number of
// steps required to reduce N to perfect
// power of 2 by performing given steps
static void findMinimumSteps(int N) {
String num = String.valueOf(N);
int c = 1;
Stack<String> a = new Stack<>();
// Stores all the perfect power of 2
while (true) {
if (c > (int)Math.pow(10, 20)|| c>10 ) {
break;
}
a.add(String.valueOf(c));
c = c * 2;
}
// Maximum number of steps required
int best = num.length()+1;
// Iterate for each perfect power of 2
String x;
int i = 0;
while (!a.isEmpty()) {
x = a.pop();
int position = 0;
// Comparing with all numbers
for (i = 0; i < num.length(); i++) {
if (position < x.length() && x.charAt(position) == num.charAt(i))
position += 1;
}
// Update the minimum number of
// steps required
best = (int) (Math.min(best, x.length() + num.length() - 2 * position));
}
// Print the result
System.out.print(best-1);
}
// Driver Code
public static void main(String[] args) {
int N = 1092;
// Function Call
findMinimumSteps(N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program for the above approach # Function to find the minimum number of # steps required to reduce N to perfect # power of 2 by performing given steps def findMinimumSteps(N): num = str(N) c = 1 a = [] # Stores all the perfect power of 2 while True: if (c > 10 ** 20): break a.append(str(c)) c = c * 2 # Maximum number of steps required best = len(num) + 1 # Iterate for each perfect power of 2 for x in a: position = 0 # Comparing with all numbers for i in range(len(num)): if position < len(x) and x[position] == num[i]: position += 1 # Update the minimum number of # steps required best = min(best, len(x) + len(num) - 2 * position) # Print the result print(best) # Driver Code N = 1092 # Function Call findMinimumSteps(N)
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number of
// steps required to reduce N to perfect
// power of 2 by performing given steps
function findMinimumSteps(N)
{
num = N.toString()
c = 1
a = []
// Stores all the perfect power of 2
while (1) {
if (c > Math.pow(10, 20)) {
break;
}
a.push(c.toString())
c = c * 2
}
// Maximum number of steps required
best = num.length + 1
// Iterate for each perfect power of 2
for (x of a) {
position = 0
// Comparing with all numbers
for (let i = 0; i < num.length; i++) {
if (position < x.length && x[position] == num[i])
position += 1
}
// Update the minimum number of
// steps required
best = Math.min(best, x.length + num.length - 2 * position)
}
// Print the result
document.write(best)
}
// Driver Code
let N = 1092
// Function Call
findMinimumSteps(N)
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)