Recuento de elementos de array de bits pares e impares después de XOR con K para consultas Q

Dada una array arr de N elementos y otra array Q que contiene valores de K , la tarea es imprimir el recuento de elementos en la array arr con bits pares e impares después de su XOR con cada elemento K en la array Q .

Ejemplos: 

Entrada: arr[] = { 2, 7, 4, 5, 3 }, Q[] = { 3, 4, 12, 6 } 
Salida: 2 3 
3 2 
2 3 
2 3

Entrada: arr[] = { 7, 1, 6, 5, 11 }, Q[] = { 2, 10, 3, 6 } 
Salida: 3 2 
2 3 
2 3 
2 3 
 

Acercarse:  

• XOR de dos elementos que tienen bits establecidos pares o impares, da como resultado bits establecidos pares.
• XOR de dos elementos, uno con bits impares y el otro con bits pares o viceversa, da como resultado bits impares.
• Calcule previamente el recuento de elementos con bits de conjuntos pares e impares de todos los elementos de la array mediante el algoritmo de Brian Kernighan.
• Para todos los elementos de Q, cuente el número de bits establecidos. Si el recuento de bits establecidos es par, el recuento de elementos de bits establecidos pares e impares permanece sin cambios. De lo contrario, invierta el conteo y la pantalla.

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

// C++ Program to count number
// of even and odd set bits
// elements after XOR with a
// given element
 
#include <bits/stdc++.h>
using namespace std;
 
void keep_count(int arr[], int& even,
                int& odd, int N)
{
    // Store the count of set bits
    int count;
    for (int i = 0; i < N; i++) {
        count = 0;
 
        // Brian Kernighan's algorithm
        while (arr[i] != 0) {
            arr[i] = (arr[i] - 1) & arr[i];
            count++;
        }
 
        if (count % 2 == 0)
            even++;
        else
            odd++;
    }
 
    return;
}
 
// Function to solve Q queries
void solveQueries(
    int arr[], int n,
    int q[], int m)
{
 
    int even_count = 0, odd_count = 0;
 
    keep_count(arr, even_count,
               odd_count, n);
 
    for (int i = 0; i < m; i++) {
 
        int X = q[i];
 
        // Store set bits in X
        int count = 0;
 
        // Count set bits of X
        while (X != 0) {
            X = (X - 1) & X;
            count++;
        }
 
        if (count % 2 == 0) {
            cout << even_count << " "
                 << odd_count << "\n";
        }
        else {
            cout << odd_count << " "
                 << even_count
                 << "\n";
        }
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, 7, 4, 5, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int q[] = { 3, 4, 12, 6 };
    int m = sizeof(q) / sizeof(q[0]);
 
    solveQueries(arr, n, q, m);
 
    return 0;
}

// Java program to count number
// of even and odd set bits
// elements after XOR with a
// given element
class GFG{
     
static int even, odd;
 
static void keep_count(int arr[], int N)
{
     
    // Store the count of set bits
    int count;
     
    for(int i = 0; i < N; i++)
    {
       count = 0;
        
       // Brian Kernighan's algorithm
       while (arr[i] != 0)
       {
           arr[i] = (arr[i] - 1) & arr[i];
           count++;
       }
       if (count % 2 == 0)
           even++;
       else
           odd++;
    }
    return;
}
 
// Function to solve Q queries
static void solveQueries(int arr[], int n,
                         int q[], int m)
{
    even = 0;
    odd = 0;
    keep_count(arr, n);
 
    for(int i = 0; i < m; i++)
    {
       int X = q[i];
        
       // Store set bits in X
       int count = 0;
        
       // Count set bits of X
       while (X != 0)
       {
           X = (X - 1) & X;
           count++;
       }
       if (count % 2 == 0)
       {
           System.out.print(even + " " +
                             odd + "\n");
       }
       else
       {
           System.out.print(odd + " " +
                           even + "\n");
       }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 7, 4, 5, 3 };
    int n = arr.length;
 
    int q[] = { 3, 4, 12, 6 };
    int m = q.length;
 
    solveQueries(arr, n, q, m);
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program to count number
# of even and odd set bits
# elements after XOR with a
# given element
 
even = 0
odd = 0
 
def keep_count(arr, N):
     
    global even
    global odd
     
    # Store the count of set bits
    for i in range(N):
        count = 0
 
        # Brian Kernighan's algorithm
        while (arr[i] != 0):
            arr[i] = (arr[i] - 1) & arr[i]
            count += 1
 
        if (count % 2 == 0):
            even += 1
        else:
            odd += 1
 
    return
 
# Function to solve Q queries
def solveQueries(arr, n, q, m):
     
    global even
    global odd
     
    keep_count(arr, n)
 
    for i in range(m):
        X = q[i]
 
        # Store set bits in X
        count = 0
 
        # Count set bits of X
        while (X != 0):
            X = (X - 1) & X
            count += 1
 
        if (count % 2 == 0):
            print(even, odd)
        else:
            print(odd, even)
 
# Driver code
if __name__ == '__main__':
     
    arr = [ 2, 7, 4, 5, 3 ]
    n = len(arr)
 
    q = [ 3, 4, 12, 6 ]
    m = len(q)
 
    solveQueries(arr, n, q, m)
 
# This code is contributed by samarth

// C# program to count number
// of even and odd set bits
// elements after XOR with a
// given element
using System;
class GFG{
     
static int even, odd;
 
static void keep_count(int []arr, int N)
{
     
    // Store the count of set bits
    int count;
     
    for(int i = 0; i < N; i++)
    {
        count = 0;
             
        // Brian Kernighan's algorithm
        while (arr[i] != 0)
        {
            arr[i] = (arr[i] - 1) & arr[i];
            count++;
        }
        if (count % 2 == 0)
            even++;
        else
            odd++;
    }
    return;
}
 
// Function to solve Q queries
static void solveQueries(int []arr, int n,
                         int []q, int m)
{
    even = 0;
    odd = 0;
    keep_count(arr, n);
 
    for(int i = 0; i < m; i++)
    {
        int X = q[i];
             
        // Store set bits in X
        int count = 0;
             
        // Count set bits of X
        while (X != 0)
        {
            X = (X - 1) & X;
            count++;
        }
        if (count % 2 == 0)
        {
            Console.Write(even + " " +
                           odd + "\n");
        }
        else
        {
            Console.Write(odd + " " +
                         even + "\n");
        }
    }
}
 
// Driver code
public static void Main()
{
    int []arr = { 2, 7, 4, 5, 3 };
    int n = arr.Length;
 
    int []q = { 3, 4, 12, 6 };
    int m = q.Length;
 
    solveQueries(arr, n, q, m);
}
}
 
// This code is contributed by Code_Mech

<script>
 
// Javascript program to count number
// of even and odd set bits
// elements after XOR with a
// given element function even, odd;
function keep_count(arr, N)
{
     
    // Store the count of set bits
    var count;
 
    for(i = 0; i < N; i++)
    {
        count = 0;
         
        // Brian Kernighan's algorithm
        while (arr[i] != 0)
        {
            arr[i] = (arr[i] - 1) & arr[i];
            count++;
        }
        if (count % 2 == 0)
            even++;
        else
            odd++;
    }
    return;
}
 
// Function to solve Q queries
function solveQueries(arr, n, q, m)
{
    even = 0;
    odd = 0;
    keep_count(arr, n);
 
    for(i = 0; i < m; i++)
    {
        var X = q[i];
 
        // Store set bits in X
        var count = 0;
 
        // Count set bits of X
        while (X != 0)
        {
            X = (X - 1) & X;
            count++;
        }
        if (count % 2 == 0)
        {
            document.write(even + " " +
                            odd + "<br/>");
        }
        else
        {
            document.write(odd + " " +
                          even + "<br/>");
        }
    }
}
 
// Driver code
var arr = [ 2, 7, 4, 5, 3 ];
var n = arr.length;
 
var q = [ 3, 4, 12, 6 ];
var m = q.length;
 
solveQueries(arr, n, q, m);
 
// This code is contributed by aashish1995
 
</script>

2 3
3 2
2 3
2 3

Complejidad de tiempo: O(N * log N)