Dados dos arreglos A[] y B[] que tienen N y M elementos positivos respectivamente. La tarea es contar la cantidad de elementos en la array A con un número par de bits establecidos en XOR para cada elemento de la array B.
Ejemplos:
Entrada: A[] = { 4, 2, 15, 9, 8, 8 }, B[] = { 3, 4, 22 }
Salida: 2 4 4
Explicación:
La representación binaria de los elementos de A son: 100, 10, 1111, 1001, 1000, 1000
La representación binaria de los elementos de B son: 11, 101, 10110
Ahora para el elemento 3(11),
3^4 = 11^100 = 111
3^2 = 11^10 = 01
3^15 = 11^1111 = 1100
3^9 = 11^1001 = 1111
3^8 = 11^1000 = 1011
3^8 = 11^1000 = 1011
Solo hay 2 elementos {15, 9} en A[] para el elemento 3 tales ese recuento de bits establecidos después de XOR es par. Por lo tanto, la cuenta es 2.
De manera similar, la cuenta para el elemento 4 y 22 es 4.
Entrada: A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, B[] = { 4 }
Salida: 5
Explicación:
el elemento en A[] tal que el recuento de bits establecidos después de XOR es par {1, 2, 4, 7, 8}. Entonces la cuenta es 5.
Enfoque ingenuo: la idea es calcular el XOR para cada elemento de la array B[] con cada elemento de la array A[] y contar el número con un bit par establecido.
Complejidad de tiempo: O(N*M), donde N y M son la longitud de la array A[] y B[] respectivamente.
Enfoque eficiente: la idea es utilizar la propiedad de XOR. Para dos números cualquiera, si el conteo de bits establecidos para ambos números es par o impar, entonces el conteo de bits establecidos después de XOR de ambos números es par .
A continuación se muestran los pasos basados en la propiedad anterior:
- Cuente el número de elementos en la array A[] que tiene un número par (digamos a ) e impar (digamos b ) de bits establecidos.
- Para cada elemento en la array B[] :
- Si el elemento actual tiene un conteo par de bits establecidos, entonces el elemento numérico en la array A[] cuyo XOR con el elemento actual tiene un conteo par de bits establecidos es un .
- Si el elemento actual tiene un conteo impar de bits establecidos, entonces el elemento numérico en la array A[] cuyo XOR con el elemento actual tiene un conteo par de bits establecidos es b .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that count the XOR of B[]
// with all the element in A[] having
// even set bit
void countEvenBit(int A[], int B[], int n, int m)
{
int i, j, cntOdd = 0, cntEven = 0;
for (i = 0; i < n; i++) {
// Count the set bits in A[i]
int x = __builtin_popcount(A[i]);
// check for even or Odd
if (x & 1) {
cntEven++;
}
else {
cntOdd++;
}
}
// To store the count of element for
// B[] such that XOR with all the
// element in A[] having even set bit
int CountB[m];
for (i = 0; i < m; i++) {
// Count set bit for B[i]
int x = __builtin_popcount(B[i]);
// check for Even or Odd
if (x & 1) {
CountB[i] = cntEven;
}
else {
CountB[i] = cntOdd;
}
}
for (i = 0; i < m; i++) {
cout << CountB[i] << ' ';
}
}
// Driver Code
int main()
{
int A[] = { 4, 2, 15, 9, 8, 8 };
int B[] = { 3, 4, 22 };
countEvenBit(A, B, 6, 3);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that count the XOR of B[]
// with all the element in A[] having
// even set bit
static void countEvenBit(int A[], int B[], int n, int m)
{
int i, j, cntOdd = 0, cntEven = 0;
for (i = 0; i < n; i++) {
// Count the set bits in A[i]
int x = Integer.bitCount(A[i]);
// check for even or Odd
if (x % 2 == 1) {
cntEven++;
}
else {
cntOdd++;
}
}
// To store the count of element for
// B[] such that XOR with all the
// element in A[] having even set bit
int []CountB = new int[m];
for (i = 0; i < m; i++) {
// Count set bit for B[i]
int x = Integer.bitCount(B[i]);
// check for Even or Odd
if (x%2 == 1) {
CountB[i] = cntEven;
}
else {
CountB[i] = cntOdd;
}
}
for (i = 0; i < m; i++) {
System.out.print(CountB[i] +" ");
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 4, 2, 15, 9, 8, 8 };
int B[] = { 3, 4, 22 };
countEvenBit(A, B, 6, 3);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach
# Function that count the XOR of B
# with all the element in A having
# even set bit
def countEvenBit(A, B, n, m):
i, j, cntOdd = 0, 0, 0
cntEven = 0
for i in range(n):
# Count the set bits in A[i]
x = bin(A[i])[2:].count('1')
# check for even or Odd
if (x & 1):
cntEven += 1
else :
cntOdd += 1
# To store the count of element for
# B such that XOR with all the
# element in A having even set bit
CountB = [0]*m
for i in range(m):
# Count set bit for B[i]
x = bin(B[i])[2:].count('1')
# check for Even or Odd
if (x & 1):
CountB[i] = cntEven
else:
CountB[i] = cntOdd
for i in range(m):
print(CountB[i], end=" ")
# Driver Code
if __name__ == '__main__':
A = [ 4, 2, 15, 9, 8, 8]
B = [ 3, 4, 22 ]
countEvenBit(A, B, 6, 3)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function that count the XOR of []B
// with all the element in []A having
// even set bit
static void countEvenBit(int []A, int []B, int n, int m)
{
int i, cntOdd = 0, cntEven = 0;
for (i = 0; i < n; i++)
{
// Count the set bits in A[i]
int x = bitCount(A[i]);
// check for even or Odd
if (x % 2 == 1) {
cntEven++;
}
else {
cntOdd++;
}
}
// To store the count of element for
// []B such that XOR with all the
// element in []A having even set bit
int []CountB = new int[m];
for (i = 0; i < m; i++) {
// Count set bit for B[i]
int x = bitCount(B[i]);
// check for Even or Odd
if (x % 2 == 1) {
CountB[i] = cntEven;
}
else {
CountB[i] = cntOdd;
}
}
for (i = 0; i < m; i++) {
Console.Write(CountB[i] +" ");
}
}
static int bitCount(int x)
{
int setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 4, 2, 15, 9, 8, 8 };
int []B = { 3, 4, 22 };
countEvenBit(A, B, 6, 3);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function that count the XOR of B[]
// with all the element in A[] having
// even set bit
function countEvenBit(A, B, n, m)
{
let i, j, cntOdd = 0, cntEven = 0;
for (i = 0; i < n; i++) {
// Count the set bits in A[i]
let x = bitCount(A[i]);
// check for even or Odd
if (x & 1) {
cntEven++;
}
else {
cntOdd++;
}
}
// To store the count of element for
// B[] such that XOR with all the
// element in A[] having even set bit
let CountB = new Array(m);
for (i = 0; i < m; i++) {
// Count set bit for B[i]
let x = bitCount(B[i]);
// check for Even or Odd
if (x & 1) {
CountB[i] = cntEven;
}
else {
CountB[i] = cntOdd;
}
}
for (i = 0; i < m; i++) {
document.write(CountB[i] + " ");
}
}
function bitCount(x)
{
let setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
let A = [ 4, 2, 15, 9, 8, 8 ];
let B = [ 3, 4, 22 ];
countEvenBit(A, B, 6, 3);
</script>
2 4 4
Complejidad de tiempo: O (N + M), donde N y M son la longitud de las dos arrays dadas, respectivamente.
Publicación traducida automáticamente
Artículo escrito por Sanjeevkumar32 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA