Dado un número entero N , la tarea es encontrar el número mínimo de bits necesarios para convertir la representación binaria de N en un palíndromo.
Ejemplos:
Entrada: N = 12
Salida: 2
Explicación:
String binaria que representa 12 = “1100”.
Para convertir «1100» en un palíndromo, convierta la string en «0110».
Por lo tanto, los bits mínimos necesarios para invertir son 2.
Entrada: N = 7
Salida: 0
Explicación:
String binaria que representa 7 = 111, que ya es un palíndromo.
Enfoque ingenuo: la forma más sencilla es verificar cada subconjunto posible que sea un palíndromo que tenga la misma cantidad de bits.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar a través de estos pasos:
- Primero, verifique la longitud de la forma binaria del número dado.
- Tome dos punteros uno en el LSB y otro en el MSB .
- Ahora siga disminuyendo el primer puntero e incrementando el segundo puntero.
- Compruebe si los bits en la posición del primer y segundo puntero son iguales o no. Si no, incremente el número de bits a cambiar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// length of the binary string
int check_length(int n)
{
// Length
int ans = 0;
while (n) {
// Right shift of n
n = n >> 1;
// Increment the length
ans++;
}
// Return the length
return ans;
}
// Function to check if the bit present
// at i-th position is a set bit or not
int check_ith_bit(int n, int i)
{
// Returns true if the bit is set
return (n & (1 << (i - 1)))
? true
: false;
}
// Function to count the minimum
// number of bit flips required
int no_of_flips(int n)
{
// Length of the binary form
int len = check_length(n);
// Number of flips
int ans = 0;
// Pointer to the LSB
int right = 1;
// Pointer to the MSB
int left = len;
while (right < left) {
// Check if the bits are equal
if (check_ith_bit(n, right)
!= check_ith_bit(n, left))
ans++;
// Decrementing the
// left pointer
left--;
// Incrementing the
// right pointer
right++;
}
// Returns the number of
// bits to flip.
return ans;
}
// Driver Code
int main()
{
int n = 12;
cout << no_of_flips(n);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to calculate the
// length of the binary string
static int check_length(int n)
{
// Length
int ans = 0;
while (n != 0)
{
// Right shift of n
n = n >> 1;
// Increment the length
ans++;
}
// Return the length
return ans;
}
// Function to check if the bit present
// at i-th position is a set bit or not
static boolean check_ith_bit(int n, int i)
{
// Returns true if the bit is set
return (n & (1<< (i - 1))) != 0 ? true : false;
}
// Function to count the minimum
// number of bit flips required
static int no_of_flips(int n)
{
// Length of the binary form
int len = check_length(n);
// Number of flips
int ans = 0;
// Pointer to the LSB
int right = 1;
// Pointer to the MSB
int left = len;
while (right < left)
{
// Check if the bits are equal
if (check_ith_bit(n, right) !=
check_ith_bit(n, left))
ans++;
// Decrementing the
// left pointer
left--;
// Incrementing the
// right pointer
right++;
}
// Returns the number of
// bits to flip.
return ans;
}
// Driver Code
public static void main(String[] args)
{
int n = 12;
System.out.println(no_of_flips(n));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to implement # the above approach # Function to calculate the # length of the binary string def check_length(n): # Length ans = 0 while (n): # Right shift of n n = n >> 1 # Increment the length ans += 1 # Return the length return ans # Function to check if the bit present # at i-th position is a set bit or not def check_ith_bit(n, i): # Returns true if the bit is set if (n & (1 << (i - 1))): return True else: return False # Function to count the minimum # number of bit flips required def no_of_flips(n): # Length of the binary form ln = check_length(n) # Number of flips ans = 0 # Pointer to the LSB right = 1 # Pointer to the MSB left = ln while (right < left): # Check if the bits are equal if (check_ith_bit(n, right) != check_ith_bit(n, left)): ans += 1 # Decrementing the # left pointer left -= 1 # Incrementing the # right pointer right += 1 # Returns the number of # bits to flip. return ans # Driver Code n = 12 print(no_of_flips(n)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate the
// length of the binary string
static int check_length(int n)
{
// Length
int ans = 0;
while (n != 0)
{
// Right shift of n
n = n >> 1;
// Increment the length
ans++;
}
// Return the length
return ans;
}
// Function to check if the bit present
// at i-th position is a set bit or not
static bool check_ith_bit(int n, int i)
{
// Returns true if the bit is set
return (n & (1 << (i - 1))) != 0 ?
true : false;
}
// Function to count the minimum
// number of bit flips required
static int no_of_flips(int n)
{
// Length of the binary form
int len = check_length(n);
// Number of flips
int ans = 0;
// Pointer to the LSB
int right = 1;
// Pointer to the MSB
int left = len;
while (right < left)
{
// Check if the bits are equal
if (check_ith_bit(n, right) !=
check_ith_bit(n, left))
ans++;
// Decrementing the
// left pointer
left--;
// Incrementing the
// right pointer
right++;
}
// Returns the number of
// bits to flip.
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int n = 12;
Console.WriteLine(no_of_flips(n));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate the
// length of the binary string
function check_length(n)
{
// Length
let ans = 0;
while (n != 0)
{
// Right shift of n
n = n >> 1;
// Increment the length
ans++;
}
// Return the length
return ans;
}
// Function to check if the bit present
// at i-th position is a set bit or not
function check_ith_bit(n, i)
{
// Returns true if the bit is set
return (n & (1<< (i - 1))) != 0 ? true : false;
}
// Function to count the minimum
// number of bit flips required
function no_of_flips(n)
{
// Length of the binary form
let len = check_length(n);
// Number of flips
let ans = 0;
// Pointer to the LSB
let right = 1;
// Pointer to the MSB
let left = len;
while (right < left)
{
// Check if the bits are equal
if (check_ith_bit(n, right) !=
check_ith_bit(n, left))
ans++;
// Decrementing the
// left pointer
left--;
// Incrementing the
// right pointer
right++;
}
// Returns the number of
// bits to flip.
return ans;
}
// Driver Code
let n = 12;
document.write(no_of_flips(n));
</script>
Producción:
2
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por swapnoneelmajumdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA