Cuente el número de subconjuntos que tienen un valor XOR particular

Dada una array arr[] de n números y un número K, encuentre la cantidad de subconjuntos de arr[] que tienen XOR de elementos como K
Ejemplos: 

Input:   arr[]  = {6, 9, 4,2}, k = 6
Output:  2
The subsets are {4, 2} and {6}

Input:   arr[]  = {1, 2, 3, 4, 5}, k = 4
Output:  4
The subsets are {1, 5}, {4}, {1, 2, 3, 4}
                and {2, 3, 5}

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Enfoque de fuerza bruta O(2 ⁿ ): un enfoque ingenuo es generar todos los 2 ⁿ subconjuntos y contar todos los subconjuntos que tienen el valor XOR K, pero este enfoque no será eficiente para valores grandes de n.

Enfoque de programación dinámica O(n*m): 
definimos un número m tal que m = pow(2,(log2(max(arr))+1)) – 1. Este número es en realidad el valor máximo que adquirirá cualquier subconjunto XOR . Obtenemos este número contando los bits en mayor número. Creamos una array 2D dp[n+1][m+1], tal que dp[i][j] es igual a la cantidad de subconjuntos que tienen el valor XOR j de los subconjuntos de arr[0…i-1] .

Rellenamos la array dp de la siguiente manera: 

1. Inicializamos todos los valores de dp[i][j] como 0.
2. Establecer el valor de dp[0][0] = 1 ya que XOR de un conjunto vacío es 0.
3. Iterar sobre todos los valores de arr[i] de izquierda a derecha y para cada arr[i], iterar sobre todos los valores posibles de XOR, es decir, de 0 a m (ambos inclusive) y llenar la array dp de la siguiente manera: para i = 
          1 a n: 
                para j = 0 a m: 
                      dp[i][j] = dp[i-1][j] + dp[i-1][j^arr[i-1]] Esto se puede explicar como 
   , si hay un subconjunto arr[0…i-2] con valor XOR j, entonces también existe un subconjunto arr[0…i-1] con valor XOR j. también si existe un subconjunto arr[0….i-2] con valor XOR j^arr[i] entonces claramente existe un subconjunto arr[0…i-1] con valor XOR j, como j ^ arr[i- 1] ^ arr[i-1] = j.
4. Contar el número de subconjuntos con valor XOR k: Dado que dp[i][j] es el número de subconjuntos que tienen j como valor XOR de los subconjuntos de arr[0..i-1], entonces el número de subconjuntos del conjunto arr [0..n] teniendo valor XOR como K será dp[n][K]

// arr dynamic programming solution to finding the number
// of subsets having xor of their elements as k
#include <bits/stdc++.h>
using namespace std;
 
// Returns count of subsets of arr[] with XOR value equals
// to k.
int subsetXOR(int arr[], int n, int k)
{
    // Find maximum element in arr[]
    int max_ele = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max_ele)
            max_ele = arr[i];
 
    // Maximum possible XOR value
    int m = (1 << (int)(log2(max_ele) + 1)) - 1;
    if (k > m)
        return 0;
    // The value of dp[i][j] is the number of subsets having
    // XOR of their elements as j from the set arr[0...i-1]
    int dp[n + 1][m + 1];
 
    // Initializing all the values of dp[i][j] as 0
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;
 
    // The xor of empty subset is 0
    dp[0][0] = 1;
 
    // Fill the dp table
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j]
                = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]];
 
    //  The answer is the number of subset from set
    //  arr[0..n-1] having XOR of elements as k
    return dp[n][k];
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subsets is " << subsetXOR(arr, n, k);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// arr dynamic programming solution to finding the number
// of subsets having xor of their elements as k
#include <math.h>
#include <stdio.h>
 
// Returns count of subsets of arr[] with XOR value
// equals to k.
int subsetXOR(int arr[], int n, int k)
{
    // Find maximum element in arr[]
    int max_ele = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max_ele)
            max_ele = arr[i];
 
    // Maximum possible XOR value
    int m = (1 << (int)(log2(max_ele) + 1)) - 1;
    if (k > m)
        return 0;
    // The value of dp[i][j] is the number of subsets having
    // XOR of their elements as j from the set arr[0...i-1]
    int dp[n + 1][m + 1];
 
    // Initializing all the values of dp[i][j] as 0
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;
 
    // The xor of empty subset is 0
    dp[0][0] = 1;
 
    // Fill the dp table
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j]
                = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]];
 
    //  The answer is the number of subset from set
    //  arr[0..n-1] having XOR of elements as k
    return dp[n][k];
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Count of subsets is %d", subsetXOR(arr, n, k));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java dynamic programming solution to finding the number
// of subsets having xor of their elements as k
class GFG {
 
    // Returns count of subsets of arr[] with XOR value
    // equals to k.
    static int subsetXOR(int[] arr, int n, int k)
    {
 
        // Find maximum element in arr[]
        int max_ele = arr[0];
 
        for (int i = 1; i < n; i++)
            if (arr[i] > max_ele)
                max_ele = arr[i];
 
        // Maximum possible XOR value
        int m = (1 << (int)(Math.log(max_ele) / Math.log(2) + 1)) - 1;
        if (k > m)
            return 0;
 
        // The value of dp[i][j] is the number of subsets
        // having XOR of their elements as j from the set
        // arr[0...i-1]
        int[][] dp = new int[n + 1][m + 1];
 
        // Initializing all the values of dp[i][j] as 0
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j] = 0;
 
        // The xor of empty subset is 0
        dp[0][0] = 1;
 
        // Fill the dp table
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]];
 
        // The answer is the number of subset from set
        // arr[0..n-1] having XOR of elements as k
        return dp[n][k];
    }
 
    // Driver code
    public static void main(String arg[])
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int k = 4;
        int n = arr.length;
 
        System.out.println("Count of subsets is " + subsetXOR(arr, n, k));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python 3 arr dynamic programming solution
# to finding the number of subsets having
# xor of their elements as k
import math
 
# Returns count of subsets of arr[] with
# XOR value equals to k.
def subsetXOR(arr, n, k):
     
    # Find maximum element in arr[]
    max_ele = arr[0]
    for i in range(1, n):
        if arr[i] > max_ele :
            max_ele = arr[i]
             
    # Maximum possible XOR value
    m = (1 << (int)(math.log2(max_ele) + 1)) - 1
    if( k > m  ):
       return 0
 
 
    # The value of dp[i][j] is the number
    # of subsets having XOR of their elements
    # as j from the set arr[0...i-1]
 
    # Initializing all the values
    # of dp[i][j] as 0
    dp = [[0 for i in range(m + 1)]
             for i in range(n + 1)]
     
    # The xor of empty subset is 0
    dp[0][0] = 1
 
    # Fill the dp table
    for i in range(1, n + 1):
        for j in range(m + 1):
            dp[i][j] = (dp[i - 1][j] +
                        dp[i - 1][j ^ arr[i - 1]])
 
    # The answer is the number of subset
    # from set arr[0..n-1] having XOR of
    # elements as k
    return dp[n][k]
 
# Driver Code
arr = [1, 2, 3, 4, 5]
k = 4
n = len(arr)
print("Count of subsets is",
       subsetXOR(arr, n, k))
 
# This code is contributed
# by sahishelangia

// C# dynamic programming solution to finding the number
// of subsets having xor of their elements as k
using System;
 
class GFG
{
     
// Returns count of subsets of arr[] with
// XOR value equals to k.
static int subsetXOR(int []arr, int n, int k)
{
    // Find maximum element in arr[]
    int max_ele = arr[0];
    for (int i = 1; i < n; i++)
    if (arr[i] > max_ele)
        max_ele = arr[i];
 
    // Maximum possible XOR value
    int m = (1 << (int)(Math.Log(max_ele,2) + 1) ) - 1;
    if( k > m  ){
       return 0; 
    }
    // The value of dp[i][j] is the number of subsets having
    // XOR of their elements as j from the set arr[0...i-1]
    int [,]dp=new int[n+1,m+1];
 
    // Initializing all the values of dp[i][j] as 0
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i, j] = 0;
 
    // The xor of empty subset is 0
    dp[0, 0] = 1;
 
    // Fill the dp table
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i, j] = dp[i-1, j] + dp[i-1, j^arr[i-1]];
 
    // The answer is the number of subset from set
    // arr[0..n-1] having XOR of elements as k
    return dp[n, k];
}
 
    // Driver code
    static public void Main ()
    {
        int []arr = {1, 2, 3, 4, 5};
        int k = 4;
        int n = arr.Length;
        Console.WriteLine ("Count of subsets is " + subsetXOR(arr, n, k));
    }
}
 
// This code is contributed by jit_t.

<?php
// PHP arr dynamic programming
// solution to finding the number
// of subsets having xor of their
// elements as k
 
// Returns count of subsets of
// arr[] with XOR value equals to k.
function subsetXOR($arr, $n, $k)
{
    // Find maximum element in arr[]
    $max_ele = $arr[0];
    for ($i = 1; $i < $n; $i++)
    if ($arr[$i] > $max_ele)
        $max_ele = $arr[$i];
 
    // Maximum possible XOR value
    $m = (1 << (int)(log($max_ele,
                    2) + 1) ) - 1;
    if( $k > $m  ){
       return 0;
    }
    // The value of dp[i][j] is the
    // number of subsets having
    // XOR of their elements as j
    // from the set arr[0...i-1]
     
    // Initializing all the
    // values of dp[i][j] as 0
    for ($i = 0; $i <= $n; $i++)
        for ($j = 0; $j <= $m; $j++)
            $dp[$i][$j] = 0;
 
    // The xor of empty subset is 0
    $dp[0][0] = 1;
 
    // Fill the dp table
    for ($i = 1; $i <= $n; $i++)
        for ( $j = 0; $j <= $m; $j++)
            $dp[$i][$j] = $dp[$i - 1][$j] +
                          $dp[$i - 1][$j ^
                          $arr[$i - 1]];
 
    // The answer is the number
    // of subset from set arr[0..n-1]
    // having XOR of elements as k
    return $dp[$n][$k];
}
 
// Driver Code
$arr = array (1, 2, 3, 4, 5);
$k = 4;
$n = sizeof($arr);
echo "Count of subsets is " ,
     subsetXOR($arr, $n, $k);
 
// This code is contributed by ajit
?>

<script>
 
    // Javascript dynamic programming solution
    // to finding the number of subsets
    // having xor of their elements as k
       
    // Returns count of subsets of arr[] with
    // XOR value equals to k.
    function subsetXOR(arr, n, k)
    {
 
        // Find maximum element in arr[]
        let max_ele = arr[0];
 
        for(let i = 1; i < n; i++)
            if (arr[i] > max_ele)
                max_ele = arr[i];
 
        // Maximum possible XOR value
        let m = (1 << parseInt(Math.log(max_ele) /
        Math.log(2) + 1, 10) ) - 1;
        if (k > m)
        {
           return 0; 
        }
 
        // The value of dp[i][j] is the number
        // of subsets having XOR of their
        // elements as j from the set arr[0...i-1]
        let dp = new Array(n + 1);
 
        // Initializing all the values of dp[i][j] as 0
        for(let i = 0; i <= n; i++)
        {
            dp[i] = new Array(m + 1);
            for(let j = 0; j <= m; j++)
            {
                dp[i][j] = 0;
            }
        }
 
        // The xor of empty subset is 0
        dp[0][0] = 1;
 
        // Fill the dp table
        for(let i = 1; i <= n; i++)
            for(let j = 0; j <= m; j++)
                dp[i][j] = dp[i - 1][j] +
                dp[i - 1][j ^ arr[i - 1]];
 
        // The answer is the number of
        // subset from set arr[0..n-1]
        // having XOR of elements as k
        return dp[n][k];
    }
     
    let arr = [ 1, 2, 3, 4, 5 ];
    let k = 4;
    let n = arr.length;
      
    document.write("Count of subsets is " + subsetXOR(arr, n, k));
     
</script>

Producción : 

Count of subsets is 4

Complejidad temporal: O(n * m)

Espacio Auxiliar: O(n * m)

Este artículo es una contribución de Pranay Pandey . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.