Recuento de bits conjuntos pares e impares con elemento de array después de XOR con K

Posted on by Rudeus Greyrat

Dada una array arr[] y un número K . La tarea es encontrar el recuento del elemento que tiene un número par e impar del conjunto de bits después de tomar XOR de K con cada elemento del arr[] dado .
Ejemplos: 
 

Entrada: arr[] = {4, 2, 15, 9, 8, 8}, K = 3 
Salida: Par = 2, Impar = 4 
Explicación: 
La representación binaria del elemento después de tomar XOR con K es: 
4 ^ 3 = 7 (111) 
2 ^ 3 = 1 (1) 
15 ^ 3 = 12 (1100) 
9 ^ 3 = 10 (1010) 
8 ^ 3 = 11 (1011) 
8 ^ 3 = 11 (1011) 
Nº de elementos con par número de 1 en representación binaria: 2 (12, 10) 
Número de elementos con número impar de 1 en representación binaria: 4 (7, 1, 11, 11)
Entrada: arr[] = {4, 2, 15, 9, 8, 8}, K = 6 
Salida: par = 4, impar = 2 
 

Enfoque ingenuo: el enfoque ingenuo es tomar XOR bit a bit de K con cada elemento de la array dada arr[] y luego contar el bit establecido para cada elemento en la array después de tomar XOR con K .
Complejidad de Tiempo: O(N*K)
Enfoque Eficiente: 
Con la ayuda de la siguiente observación, tenemos: 
 

Por ejemplo: 
Si A = 4 y K = 3 
Representación binaria: 
A = 100 
K = 011 
A^K = 111 
Por lo tanto, el XOR del número A (que tiene un número impar de bits establecidos) con el número K (que tiene un número par de bits establecidos) da como resultado un número impar de bits establecidos. 
Y si A = 4 y K = 7 
Representación binaria: 
A = 100 
K = 111 
A^K = 011 
Por lo tanto, el XOR del número A (que tiene un número impar de set-bit) con el número K (que tiene un número impar número de set-bit) da como resultado un número par de set-bit. 
 

De las observaciones anteriores: 
 

  • Si K tiene un número impar de bits establecidos, entonces el conteo de elementos de la array arr[] con bits establecidos pares e impares después de tomar XOR con K , será el mismo que el conteo de bits establecidos pares e impares set-bit int la array antes de XOR.
  • Si K tiene un número par de bits establecidos, entonces el conteo de elementos de la array arr[] con bits establecidos pares e impares después de tomar XOR con K , se invertirá como el conteo de bits establecidos pares e impares. -bit en la array antes de XOR.

Pasos : 
 

  1. Almacene el recuento de elementos que tienen bits de configuración pares e impares de la array dada arr[] .
  2. Si K tiene un bit de configuración impar, entonces el recuento de bits de configuración pares e impares después de XOR con K será el mismo que el recuento de bits de configuración pares e impares calculado anteriormente.
  3. Si K tiene un bit de establecimiento par, entonces el recuento de bits de establecimiento pares e impares después de XOR con K será el recuento de bits de establecimiento pares e impares calculado anteriormente.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to count the set
// bits after taking XOR with a
// number K
#include <bits/stdc++.h>
using namespace std;
 
// Function to store EVEN and odd variable
void countEvenOdd(int arr[], int n, int K)
{
    int even = 0, odd = 0;
 
    // Store the count of even and
    // odd set bit
    for (int i = 0; i < n; i++) {
 
        // Count the set bit using
        // in built function
        int x = __builtin_popcount(arr[i]);
        if (x % 2 == 0)
            even++;
        else
            odd++;
    }
 
    int y;
 
    // Count of set-bit of K
    y = __builtin_popcount(K);
 
    // If y is odd then, count of
    // even and odd set bit will
    // be interchanged
    if (y & 1) {
        cout << "Even = " << odd
             << ", Odd = " << even;
    }
 
    // Else it will remain same as
    // the original array
    else {
        cout << "Even = " << even
             << ", Odd = " << odd;
    }
}
 
// Driver's Code
int main(void)
{
    int arr[] = { 4, 2, 15, 9, 8, 8 };
    int K = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to count even
    // and odd
    countEvenOdd(arr, n, K);
    return 0;
}

Java

// Java program to count the set
// bits after taking XOR with a
// number K
class GFG {
 
     
    /* Function to get no of set 
    bits in binary representation 
    of positive integer n */
    static int __builtin_popcount(int n)
    {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
     
    // Function to store EVEN and odd variable
    static void countEvenOdd(int arr[], int n, int K)
    {
        int even = 0, odd = 0;
     
        // Store the count of even and
        // odd set bit
        for (int i = 0; i < n; i++) {
     
            // Count the set bit using
            // in built function
            int x = __builtin_popcount(arr[i]);
            if (x % 2 == 0)
                even++;
            else
                odd++;
        }
     
        int y;
     
        // Count of set-bit of K
        y = __builtin_popcount(K);
     
        // If y is odd then, count of
        // even and odd set bit will
        // be interchanged
        if ((y & 1) != 0) {
            System.out.println("Even = "+ odd + ", Odd = " + even);
        }
     
        // Else it will remain same as
        // the original array
        else {
            System.out.println("Even = " + even + ", Odd = " + odd);
        }
    }
     
    // Driver's Code
    public static void main (String[] args)
    {
        int arr[] = { 4, 2, 15, 9, 8, 8 };
        int K = 3;
        int n = arr.length;
     
        // Function call to count even
        // and odd
        countEvenOdd(arr, n, K);
    }
  
}
// This code is contributed by Yash_R

Python3

# Python3 program to count the set
# bits after taking XOR with a
# number K
 
# Function to store EVEN and odd variable
def countEvenOdd(arr, n, K) :
 
    even = 0; odd = 0;
 
    # Store the count of even and
    # odd set bit
    for i in range(n) :
 
        # Count the set bit using
        # in built function
        x = bin(arr[i]).count('1');
        if (x % 2 == 0) :
            even += 1;
        else :
            odd += 1;
 
    # Count of set-bit of K
    y = bin(K).count('1');
 
    # If y is odd then, count of
    # even and odd set bit will
    # be interchanged
    if (y & 1) :
        print("Even =",odd ,", Odd =", even);
 
    # Else it will remain same as
    # the original array
    else :
        print("Even =" , even ,", Odd =", odd);
 
 
# Driver's Code
if __name__ == "__main__" :
     
    arr = [ 4, 2, 15, 9, 8, 8 ];
    K = 3;
    n = len(arr);
 
    # Function call to count even
    # and odd
    countEvenOdd(arr, n, K);
     
# This code is contributed by Yash_R

C#

// C# program to count the set
// bits after taking XOR with a
// number K
using System;
 
public class GFG {
 
     
    /* Function to get no of set 
    bits in binary representation 
    of positive integer n */
    static int __builtin_popcount(int n)
    {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
     
    // Function to store EVEN and odd variable
    static void countEvenOdd(int []arr, int n, int K)
    {
        int even = 0, odd = 0;
     
        // Store the count of even and
        // odd set bit
        for (int i = 0; i < n; i++) {
     
            // Count the set bit using
            // in built function
            int x = __builtin_popcount(arr[i]);
            if (x % 2 == 0)
                even++;
            else
                odd++;
        }
     
        int y;
     
        // Count of set-bit of K
        y = __builtin_popcount(K);
     
        // If y is odd then, count of
        // even and odd set bit will
        // be interchanged
        if ((y & 1) != 0) {
            Console.WriteLine("Even = "+ odd + ", Odd = " + even);
        }
     
        // Else it will remain same as
        // the original array
        else {
            Console.WriteLine("Even = " + even + ", Odd = " + odd);
        }
    }
     
    // Driver's Code
    public static void Main (string[] args)
    {
        int []arr = { 4, 2, 15, 9, 8, 8 };
        int K = 3;
        int n = arr.Length;
     
        // Function call to count even
        // and odd
        countEvenOdd(arr, n, K);
    }
  
}
// This code is contributed by Yash_R

Javascript

<script>
// Javascript program to count the set
// bits after taking XOR with a
// number K
 
/* Function to get no of set
bits in binary representation
of positive integer n */
function __builtin_popcount(n) {
    let count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Function to store EVEN and odd variable
function countEvenOdd(arr, n, K) {
    let even = 0, odd = 0;
 
    // Store the count of even and
    // odd set bit
    for (let i = 0; i < n; i++) {
 
        // Count the set bit using
        // in built function
        let x = __builtin_popcount(arr[i]);
        if (x % 2 == 0)
            even++;
        else
            odd++;
    }
 
    let y;
 
    // Count of set-bit of K
    y = __builtin_popcount(K);
 
    // If y is odd then, count of
    // even and odd set bit will
    // be interchanged
    if ((y & 1) != 0) {
        document.write("Even = " + odd + ", Odd = " + even);
    }
 
    // Else it will remain same as
    // the original array
    else {
        document.write("Even = " + even + ", Odd = " + odd);
    }
}
 
// Driver's Code
 
let arr = [4, 2, 15, 9, 8, 8];
let K = 3;
let n = arr.length;
 
// Function call to count even
// and odd
countEvenOdd(arr, n, K);
 
// This code is contributed by _saurabh_jaiswal
</script>
Producción: 

Even = 2, Odd = 4

 

Complejidad de tiempo: O(N)
 

Publicación traducida automáticamente

Artículo escrito por skylags y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *