Cuente las subsecuencias que tienen valores OR bit a bit impares en una array

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número de subsecuencias de la array dada cuyo valor OR bit a bit es impar.

Ejemplos:

Entrada: arr = [2, 4, 1]
Salida: 4
Explicación: Las subsecuencias con valores OR bit a bit impares son {1}, {2, 1}, {4, 1}, {2, 4, 1}

Entrada: arr = [1, 3, 4]
Salida: 6

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 OR es impar o no. Si es impar, aumente la cuenta en uno. Después de verificar todas las subsecuencias, imprima el conteo obtenido.
Tiempo Complejidad:  
Espacio Auxiliar: 

Enfoque eficiente: el problema dado se puede resolver observando que para que una subsecuencia tenga un valor OR bit a bit impar, al menos un elemento de la subsecuencia debe ser impar. Por lo tanto, al menos un elemento en la subsecuencia debe tener el dígito menos significativo igual a 1. Siga los pasos a continuación para resolver este problema:

• Almacene el recuento de elementos pares e impares presentes en la array arr [] en variables pares e impares respectivamente.
• 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 .
• Las combinaciones totales con al menos un elemento impar y cualquier número de elementos pares pueden estar dadas por: [2^(elementos impares) – 1] * 2^(elementos pares). Dado que se necesita al menos un elemento impar, se excluye un conjunto vacío de combinaciones de 1

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count the subsequences
// having odd bitwise OR value
int countSubsequences(vector<int> arr)
{
    // Stores count of odd elements
    int odd = 0;
 
    // Stores count of even elements
    int even = 0;
 
    // Traverse the array arr[]
    for (int x : arr) {
 
        // If element is odd
        if (x & 1)
            odd++;
        else
            even++;
    }
 
    // Return the final answer
    return ((1 << odd) - 1) *
              (1 << even);
}
 
// Driver Code
int main()
{
    // Given array arr[]
    vector<int> arr = {2, 4, 1};
   
    cout << countSubsequences(arr);
}

// Java implementation for the above approach
import java.io.*;
 
class GFG {
   
      // Function to count the subsequences
    // having odd bitwise OR value
    static int countSubsequences(int arr[])
    {
       
        // Stores count of odd elements
        int odd = 0;
 
        // Stores count of even elements
        int even = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < arr.length; i++) {
 
            // If element is odd
            if ((arr[i] & 1) != 0)
                odd++;
            else
                even++;
        }
 
        // Return the final answer
        return ((1 << odd) - 1) *
                  (1 << even);
    }
 
    // Driver Code
    public static void main (String[] args) {
        // Given array arr[]
        int arr[] = {2, 4, 1};
   
        System.out.println(countSubsequences(arr));
    }
}
 
// This code is contributed by Dharanendra L V.

# Python3 implementation for the above approach
 
# Function to count the subsequences
# having odd bitwise OR value
def countSubsequences(arr) :
 
    # Stores count of odd elements
    odd = 0;
 
    # Stores count of even elements
    even = 0;
 
    # Traverse the array arr[]
    for x in arr:
 
        # If element is odd
        if (x & 1) :
            odd += 1;
        else :
            even += 1;
     
    # Return the final answer
    return ((1 << odd) - 1) * (1 << even);
 
 
# Driver Code
if __name__ == "__main__" :
 
    # Given array arr[]
    arr = [2, 4, 1];
   
    print(countSubsequences(arr));
     
    # This code is contributed by AnkThon

// Java implementation for the above approach
using System;
 
class GFG {
   
      // Function to count the subsequences
    // having odd bitwise OR value
    static int countSubsequences(int []arr)
    {
       
        // Stores count of odd elements
        int odd = 0;
 
        // Stores count of even elements
        int even = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < arr.Length; i++) {
 
            // If element is odd
            if ((arr[i] & 1) != 0)
                odd++;
            else
                even++;
        }
 
        // Return the final answer
        return ((1 << odd) - 1) *
                  (1 << even);
    }
 
    // Driver Code
    public static void Main (String[] args) {
        // Given array arr[]
        int []arr = {2, 4, 1};
   
        Console.Write(countSubsequences(arr));
    }
}
 
// This code is contributed by shivanisinghss2110

    <script>
        // JavaScript Program to implement
        // the above approach
 
// Function to count the subsequences
// having odd bitwise OR value
function countSubsequences( arr)
{
 
    // Stores count of odd elements
    let odd = 0;
 
    // Stores count of even elements
    let even = 0;
 
    // Traverse the array arr[]
    for (let x of arr) {
 
        // If element is odd
        if (x & 1)
            odd++;
        else
            even++;
    }
 
    // Return the final answer
    return ((1 << odd) - 1) *
              (1 << even);
}
 
// Driver Code
 
    // Given array arr[]
    let arr = [2, 4, 1];
   
    document.write(countSubsequences(arr));
 
     // This code is contributed by Potta Lokesh
 
    </script>

4

Tiempo Complejidad: 
Espacio Auxiliar: