Dado un número entero N . La tarea es reducir el número dado N a 1 en un número mínimo de operaciones dadas. Puede realizar cualquiera de las siguientes operaciones en cada paso.
- Si el número es par entonces puedes dividir el número por 2 .
- Si el número es impar, puede realizar (N + 1) o (N – 1) .
La tarea es imprimir el número mínimo de pasos necesarios para reducir el número N a 1 realizando las operaciones anteriores.
Ejemplos:
Entrada: N = 15
Salida: 5
15 es impar 15 + 1 = 16
16 es par 16 / 2 = 8
8 es par 8 / 2 = 4
4 es par 4 / 2 = 2
2 es par 2 / 2 = 1
Entrada: N = 4
Salida: 2
Enfoque: Ya se ha discutido en este artículo un enfoque recursivo para resolver el problema anterior. En este artículo, se discutirá un enfoque incluso optimizado.
El primer paso hacia la solución es darse cuenta de que puede eliminar el LSB solo si es cero, es decir, la operación del primer tipo. Ahora, ¿qué pasa con los números impares? Uno puede pensar que solo necesita eliminar tantos 1 como sea posible para aumentar la uniformidad del número que no es correcto, por ejemplo:
111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
Y sin embargo, esta no es la mejor manera porque
111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
Tanto 111011 -> 111010 como 111011 -> 111100 eliminan el mismo número de 1, pero la segunda forma es mejor.
Por lo tanto, se debe eliminar el número máximo de 1, hacer +1 en caso de empate fallará para el caso de prueba cuando n = 3 porque 11 -> 10 -> 1 es mejor que 11 -> 100 -> 10 -> 1 . Afortunadamente, esa es la única excepción.
Así que la lógica es:
- Si N es par.
- Realice la primera operación, es decir, la división por 2 .
- Si N es impar.
- Si N = 3 o (N – 1) tiene menos 1 que (N + 1) .
- Decremento N. _
- más
- Incremento N .
- Si N = 3 o (N – 1) tiene menos 1 que (N + 1) .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number
// of set bits in n
int set_bits(int n)
{
int count = 0;
while (n) {
count += n % 2;
n /= 2;
}
return count;
}
// Function to return the minimum
// steps required to reach 1
int minSteps(int n)
{
int ans = 0;
while (n != 1) {
// If n is even then divide it by 2
if (n % 2 == 0)
n /= 2;
// If n is 3 or the number of set bits
// in (n - 1) is less than the number
// of set bits in (n + 1)
else if (n == 3
or set_bits(n - 1) < set_bits(n + 1))
n--;
else
n++;
// Increment the number of steps
ans++;
}
// Return the minimum number of steps
return ans;
}
// Driver code
int main()
{
int n = 15;
cout << minSteps(n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the number
// of set bits in n
static int set_bits(int n)
{
int count = 0;
while (n > 0)
{
count += n % 2;
n /= 2;
}
return count;
}
// Function to return the minimum
// steps required to reach 1
static int minSteps(int n)
{
int ans = 0;
while (n != 1)
{
// If n is even then divide it by 2
if (n % 2 == 0)
n /= 2;
// If n is 3 or the number of set bits
// in (n - 1) is less than the number
// of set bits in (n + 1)
else if (n == 3
|| set_bits(n - 1) < set_bits(n + 1))
n--;
else
n++;
// Increment the number of steps
ans++;
}
// Return the minimum number of steps
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 15;
System.out.print(minSteps(n));
}
}
// This code is contributed by PrinciRaj1992
Python
# Python3 implementation of the approach # Function to return the number # of set bits in n def set_bits(n): count = 0 while (n): count += n % 2 n //= 2 return count # Function to return the minimum # steps required to reach 1 def minSteps(n): ans = 0 while (n != 1): # If n is even then divide it by 2 if (n % 2 == 0): n //= 2 # If n is 3 or the number of set bits # in (n - 1) is less than the number # of set bits in (n + 1) elif (n == 3 or set_bits(n - 1) < set_bits(n + 1)): n -= 1 else: n += 1 # Increment the number of steps ans += 1 # Return the minimum number of steps return ans # Driver code n = 15 print(minSteps(n)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of set bits in n
static int set_bits(int n)
{
int count = 0;
while (n > 0)
{
count += n % 2;
n /= 2;
}
return count;
}
// Function to return the minimum
// steps required to reach 1
static int minSteps(int n)
{
int ans = 0;
while (n != 1)
{
// If n is even then divide it by 2
if (n % 2 == 0)
n /= 2;
// If n is 3 or the number of set bits
// in (n - 1) is less than the number
// of set bits in (n + 1)
else if (n == 3
|| set_bits(n - 1) < set_bits(n + 1))
n--;
else
n++;
// Increment the number of steps
ans++;
}
// Return the minimum number of steps
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 15;
Console.Write(minSteps(n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the number
// of set bits in n
function set_bits(n)
{
let count = 0;
while (n) {
count += n % 2;
n = parseInt(n / 2);
}
return count;
}
// Function to return the minimum
// steps required to reach 1
function minSteps(n)
{
let ans = 0;
while (n != 1) {
// If n is even then divide it by 2
if (n % 2 == 0)
n = parseInt(n / 2);
// If n is 3 or the number of set bits
// in (n - 1) is less than the number
// of set bits in (n + 1)
else if (n == 3
|| set_bits(n - 1) < set_bits(n + 1))
n--;
else
n++;
// Increment the number of steps
ans++;
}
// Return the minimum number of steps
return ans;
}
// Driver code
let n = 15;
document.write(minSteps(n));
</script>
5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA