Recuento mínimo de cambios de bits requeridos para hacer un palindrómico de strings binarias

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:

1. Primero, verifique la longitud de la forma binaria del número dado.
2. Tome dos punteros uno en el LSB y otro en el MSB .
3.  Ahora siga disminuyendo el primer puntero e incrementando el segundo puntero.
4. 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++ 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 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 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# 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

<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>

2

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)