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