Recuento de subsecuencias que tienen valores AND bit a bit impares en la array dada

Dada una array arr[] de N enteros, la tarea es encontrar el número de subsecuencias de la array dada de modo que su valor AND bit a bit sea impar.

Ejemplos:

Entrada: arr[] = {2, 3, 1}
Salida: 3
Explicación: Las subsecuencias de la array dada que tienen valores AND bit a bit impares son {3} = 3, {1} = 1, {3, 1} = 3 & 1 = 1.

Entrada: arr[] = {1, 3, 3}
Salida: 7

Recomendado: pruebe su enfoque en {IDE} primero, antes de pasar a la solución.

Enfoque ingenuo: el problema dado se puede resolver generando todas las subsecuencias de la array dada arr[] y realizar un seguimiento del recuento de subsecuencias de modo que su valor AND bit a bit sea impar.

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

Enfoque eficiente: el enfoque anterior puede optimizarse mediante la observación de que para que el valor AND bit a bit de un conjunto de enteros sea impar, el bit menos significativo de todos y cada uno de los elementos del conjunto debe ser un bit establecido . Por lo tanto, para que una subsecuencia tenga un valor AND bit a bit impar, todos los elementos de la subsecuencia deben ser impares. Usando esta observación, el problema dado se puede resolver siguiendo los pasos a continuación:

• Cree una variable odd , que almacene el número total de enteros impares en la array dada arr[] . Inicializarlo con 0 .
• Itere a través de la array e incremente el valor de impar en 1 si el entero actual es un entero impar.
• El recuento de subsecuencias no vacías de una array que tiene X elementos es 2 ^X – 1 . Por lo tanto, el número de subsecuencias no vacías con todos los elementos impares es 2 ^impar – 1 , que es la respuesta requerida.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find count of subsequences
// having odd bitwise AND value
int countSubsequences(vector<int> arr)
{
    // Stores count of odd elements
    int odd = 0;
 
    // Traverse the array arr[]
    for (int x : arr) {
 
        // If x is odd increment count
        if (x & 1)
            odd++;
    }
 
    // Return Answer
    return (1 << odd) - 1;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 3, 3 };
 
    // Function Call
    cout << countSubsequences(arr);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG {
 
    // Function to find count of subsequences
    // having odd bitwise AND value
    static int countSubsequences(int arr[], int N)
    {
        // Stores count of odd elements
        int odd = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < N; i++) {
 
            // If x is odd increment count
            if ((arr[i] & 1) % 2 == 1)
                odd++;
        }
 
        // Return Answer
        return (1 << odd) - 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3;
 
        int arr[] = { 1, 3, 3 };
        // Function Call
        System.out.println(countSubsequences(arr, N));
    }
}
 
// This code is contributed by dwivediyash

# python program for the above approach
 
# Function to find count of subsequences
# having odd bitwise AND value
def countSubsequences(arr):
 
    # Stores count of odd elements
    odd = 0
 
    # Traverse the array arr[]
    for x in arr:
 
        # If x is odd increment count
        if (x & 1):
            odd = odd + 1
 
    # Return Answer
    return (1 << odd) - 1
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 3, 3]
 
    # Function Call
    print(countSubsequences(arr))
     
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
 
public class GFG
{
 
    // Function to find count of subsequences
    // having odd bitwise AND value
    static int countSubsequences(int []arr, int N)
    {
       
        // Stores count of odd elements
        int odd = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < N; i++) {
 
            // If x is odd increment count
            if ((arr[i] & 1) % 2 == 1)
                odd++;
        }
 
        // Return Answer
        return (1 << odd) - 1;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 3;
 
        int []arr = { 1, 3, 3 };
         
        // Function Call
        Console.WriteLine(countSubsequences(arr, N));
    }
}
 
// This code is contributed by AnkThon

<script>
// Javascript program for the above approach
 
// Function to find count of subsequences
// having odd bitwise AND value
function countSubsequences(arr)
{
    // Stores count of odd elements
    let odd = 0;
 
    // Traverse the array arr[]
    for (let x = 0; x < arr.length; x++) {
 
        // If x is odd increment count
        if (arr[x] & 1)
            odd++;
    }
 
    // Return Answer
    return (1 << odd) - 1;
}
 
// Driver Code
    let arr = [ 1, 3, 3 ];
 
    // Function Call
    document.write(countSubsequences(arr));
 
// This code is contributed by subham348.
</script>

7

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