Cuente las subsecuencias que tienen valores impares de Bitwise XOR de una array

Dada una array A[] de tamaño N , la tarea es contar el número de subsecuencias de la array dada cuyo valor Bitwise XOR es impar.

Ejemplos:

Entrada: A[] = {1, 3, 4}
Salida: 4
Explicación: Las subsecuencias con XOR bit a bit impar son {1}, {3}, {1, 4}, {3, 4}.

Entrada: A[] = {2, 8, 6}
Salida: 0
Explicación: No existen tales subsecuencias en la array.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subsecuencias de la array dada y, para cada subsecuencia, verificar si su valor Bitwise XOR es impar o no. Si se encuentra impar, aumente el conteo en uno. Después de verificar todas las subsecuencias, imprima el conteo obtenido.

Complejidad de Tiempo: O(N * 2 ^N )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que una subsecuencia tendrá XOR bit a bit impar solo si la cantidad de elementos impares presentes en ella es impar. Esto se debe a que los elementos impares tienen el bit menos significativo igual a 1 . Por lo tanto, XOR de los bits menos significativos ( 1^1^1…. ) hasta un número impar de veces establece el bit menos significativo del nuevo número formado. Por lo tanto, el nuevo número formado es impar.
Siga los pasos a continuación para resolver el problema:

1. Almacene el recuento de elementos pares e impares presentes en la array A[] en pares e impares respectivamente.
2. Recorre la array A[] usando la variable i
   • Si el valor de A[i] es impar, aumente el valor de impar en 1.
   • De lo contrario, aumente el valor de even en 1 .
3. Si el valor de impar es igual a 0 , imprima 0 y regrese.
4. De lo contrario,
   • Encuentra las combinaciones totales con un número impar de elementos impares.
   • Esto puede ser calculado por ( ^X C ₁ + ^X C ₃ +…+ ^X C _(x-(x+1)%2) ) * ( ^M C ₀ + ^M C ₁ +…+ ^M C _M ) = 2 ^{X- 1} * 2 METRO = 2 ^{X+M-1 =} 2 N ^-1 .
   • Por lo tanto, imprime 2 ^N-1

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

// C++ program for the above approach
#include<bits/stdc++.h>
 
using namespace std;
 
// Function to count the subsequences
// having odd bitwise XOR value
void countSubsequences(vector<int> A)
{
     
    // Stores count of odd elements
    int odd = 0;
 
    // Stores count of even elements
    int even = 0;
 
    // Traverse the array A[]
    for(int el : A)
    {
         
        // If el is odd
        if (el % 2 == 1)
            odd++;
        else
            even++;
    }
 
    // If count of odd elements is 0
    if (odd == 0)
        cout << (0);
    else
        cout << (1 << (A.size() - 1));
}
 
// Driver Code
int main()
{
     
    // Given array A[]
    vector<int> A = { 1, 3, 4 };
     
    // Function call to count subsequences
    // having odd bitwise XOR value
    countSubsequences(A);
}
 
// This code is contributed by mohit kumar 29

// Java program for
// the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to count the subsequences
    // having odd bitwise XOR value
    public static void countSubsequences(int[] A)
    {
 
        // Stores count of odd elements
        int odd = 0;
 
        // Stores count of even elements
        int even = 0;
 
        // Traverse the array A[]
        for (int el : A) {
 
            // If el is odd
            if (el % 2 == 1)
                odd++;
            else
                even++;
        }
 
        // If count of odd elements is 0
        if (odd == 0)
            System.out.println(0);
 
        else
            System.out.println(1 << (A.length - 1));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array A[]
        int[] A = { 1, 3, 4 };
 
        // Function call to count subsequences
        // having odd bitwise XOR value
        countSubsequences(A);
    }
}

# Python3 program for the above approach
 
# Function to count the subsequences
# having odd bitwise XOR value
def countSubsequences(A):
     
    # Stores count of odd elements
    odd = 0
 
    # Stores count of even elements
    even = 0
 
    # Traverse the array A[]
    for el in A:
 
        # If el is odd
        if (el % 2 == 1):
            odd += 1
        else:
            even += 1
 
    # If count of odd elements is 0
    if (odd == 0):
        print(0)
    else:
        print(1 << len(A) - 1)
 
# Driver Code
if __name__ == "__main__":
 
    # Given array A[]
    A = [1, 3, 4]
 
    # Function call to count subsequences
    # having odd bitwise XOR value
    countSubsequences(A)
 
# This code is contributed by ukasp

// C# program for above approach
using System;
 
public class GFG
{
   
  // Function to count the subsequences
  // having odd bitwise XOR value
  public static void countSubsequences(int[] A)
  {
 
    // Stores count of odd elements
    int odd = 0;
 
    // Stores count of even elements
    int even = 0;
 
    // Traverse the array A[]
    foreach (int el in A) {
 
      // If el is odd
      if (el % 2 == 1)
        odd++;
      else
        even++;
    }
 
    // If count of odd elements is 0
    if (odd == 0)
      Console.WriteLine(0);
 
    else
      Console.WriteLine(1 << (A.Length - 1));
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    // Given array A[]
    int[] A = { 1, 3, 4 };
 
    // Function call to count subsequences
    // having odd bitwise XOR value
    countSubsequences(A);
  }
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript program for the above approach
 
// Function to count the subsequences
// having odd bitwise XOR value
function countSubsequences( A)
{
     
    // Stores count of odd elements
    var odd = 0;
 
    // Stores count of even elements
    var even = 0;
 
    // Traverse the array A[]
    for(var e1 = 0; e1<A.length; e1++)
    {
        // If el is odd
        if (A[e1] % 2 == 1)
            odd++;
        else
            even++;
    }
 
    // If count of odd elements is 0
    if (odd == 0)
        document.write(0);
    else
        document.write((1 << (A.length - 1)));
}
 
// Driver Code
// Given array A[]
var A = [ 1, 3, 4 ];
 
// Function call to count subsequences
// having odd bitwise XOR value
countSubsequences(A);
 
</script>

4

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