Dada una array arr[] de n elementos y un número K , encuentre el número de subconjuntos ordenados de arr[] que tienen XOR de elementos como K
Esta es una versión modificada de este problema. Por lo que se recomienda probar ese problema antes.
Ejemplos:
Entrada: arr[] = {6, 9, 4, 2}, k = 6
Salida: 2
Los subconjuntos son {4, 2}, {2, 4} y {6}
Entrada: arr[] = {1, 2 , 3}, k = 1
Salida: 4
Los subconjuntos son {1}, {2, 3} y {3, 2}
Enfoque ingenuo O (2 n ): genere todos los 2 n subconjuntos y encuentre todos los subconjuntos que tengan el valor XOR K y para cada subconjunto con el valor XOR K, agregue no. de permutaciones de ese subconjunto a la respuesta ya que se requieren subconjuntos ordenados, pero este enfoque no será eficiente para valores grandes de n.
Enfoque eficiente O(n 2 * m): este enfoque utiliza programación dinámica que es similar al enfoque explicado en este artículo.
La única modificación es que agregamos un estado más a nuestra solución. Allí teníamos dos estados donde dp[i][j] almacenaba el no. de subconjuntos del arreglo[0…i-1] que tienen el valor XOR j. Ahora, agregamos un estado k más , es decir, una tercera dimensión que almacena la longitud de los subconjuntos.
Entonces, dp[i][j][k] almacenará el no. de subconjuntos de longitud k del arreglo[0…i-1] que tienen el valor XOR j .
Ahora podemos ver que,
![$$ dp[i][j][k] = dp[i-1][j][k] + k*dp[i-1][a[i-1] XOR j][k-1] $$](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-7b1cc8e574c00e599df486e249043abf_l3.png "Rendered by QuickLaTeX.com")
es decir , dp[i][j][k] se puede encontrar descartando el elemento a[i] (que da subconjuntos dp[i-1][j][k]) y tomándolo en el subconjunto (idea similar a Subset Problema de suma) que da dp[i-1][a[i] ^ j][k-1] subconjuntos. Ahora tenemos que insertar el elemento a[i] en los k – 1 subconjuntos de longitud, lo que se puede hacer de k maneras, lo que explica el factor de k.
Después de calcular la array dp , nuestra respuesta será ![$\sum_{k=1}^{k=n} dp[n][K][k] $](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-49db66d03d772010f1aee4d0efcfd6bf_l3.png "Procesado por QuickLaTeX.com")
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Returns count of ordered subsets of arr[]
// with XOR value = 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;
// The value of dp[i][j][k] is the number
// of subsets of length k having XOR of their
// elements as j from the set arr[0...i-1]
int dp[n + 1][m + 1][n + 1];
// Initializing all the values of dp[i][j][k]
// as 0
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= n; k++)
dp[i][j][k] = 0;
// The xor of empty subset is 0
for (int i = 0; i <= n; i++)
dp[i][0][0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (k != 0) {
dp[i][j][k] += k * dp[i - 1][j ^
arr[i - 1]][k - 1];
}
}
}
}
// The answer is the number of subsets of all lengths
// from set arr[0..n-1] having XOR of elements as k
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += dp[n][K][i];
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 2, 3 };
int k = 1;
int n = sizeof(arr) / sizeof(arr[0]);
cout << subsetXOR(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Returns count of ordered subsets of arr[]
// with XOR value = 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;
// The value of dp[i][j][k] is the number
// of subsets of length k having XOR of their
// elements as j from the set arr[0...i-1]
int [][][] dp = new int[n + 1][m + 1][n + 1];
// Initializing all the values of
// dp[i][j][k] as 0
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= n; k++)
dp[i][j][k] = 0;
// The xor of empty subset is 0
for (int i = 0; i <= n; i++)
dp[i][0][0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= n; k++)
{
dp[i][j][k] = dp[i - 1][j][k];
if (k != 0)
{
dp[i][j][k] += k * dp[i - 1][j ^
arr[i - 1]][k - 1];
}
}
}
}
// The answer is the number of subsets
// of all lengths from set arr[0..n-1]
// having XOR of elements as k
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += dp[n][K][i];
}
return ans;
}
// Driver code
public static void main(String []args)
{
int arr[] = { 1, 2, 3 };
int k = 1;
int n = arr.length;
System.out.println(subsetXOR(arr, n, k));
}
}
// This code is contributed by ihritik
Python3
# Python 3implementation of the approach from math import log2 # Returns count of ordered subsets of arr[] # with XOR value = 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(log2(max_ele) + 1)) - 1 # The value of dp[i][j][k] is the number # of subsets of length k having XOR of their # elements as j from the set arr[0...i-1] dp = [[[0 for i in range(n + 1)] for j in range(m + 1)] for k in range(n + 1)] # Initializing all the values # of dp[i][j][k] as 0 for i in range(n + 1): for j in range(m + 1): for k in range(n + 1): dp[i][j][k] = 0 # The xor of empty subset is 0 for i in range(n + 1): dp[i][0][0] = 1 # Fill the dp table for i in range(1, n + 1): for j in range(m + 1): for k in range(n + 1): dp[i][j][k] = dp[i - 1][j][k] if (k != 0): dp[i][j][k] += k * dp[i - 1][j ^ arr[i - 1]][k - 1] # The answer is the number of subsets of all lengths # from set arr[0..n-1] having XOR of elements as k ans = 0 for i in range(1, n + 1): ans += dp[n][K][i] return ans # Driver Code if __name__ == '__main__': arr = [1, 2, 3] k = 1 n = len(arr) print(subsetXOR(arr, n, k)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Returns count of ordered subsets of arr[]
// with XOR value = 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;
// The value of dp[i][j][k] is the number
// of subsets of length k having XOR of their
// elements as j from the set arr[0...i-1]
int [ , , ] dp = new int[n + 1 , m + 1 ,n + 1];
// Initializing all the values of
// dp[i][j][k] as 0
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= n; k++)
dp[i, j, k] = 0;
// The xor of empty subset is 0
for (int i = 0; i <= n; i++)
dp[i, 0, 0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= n; k++)
{
dp[i, j, k] = dp[i - 1, j, k];
if (k != 0) {
dp[i, j, k] += k * dp[i - 1, j ^
arr[i - 1], k - 1];
}
}
}
}
// The answer is the number of subsets
// of all lengths from set arr[0..n-1]
// having XOR of elements as k
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += dp[n, K, i];
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 3 };
int k = 1;
int n = arr.Length;
Console.WriteLine(subsetXOR(arr, n, k));
}
}
// This code is contributed by ihritik
PHP
<?php
// Php implementation of above approach
// Returns count of ordered subsets
// of arr[] with XOR value = 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 << (floor(log($max_ele, 2))+ 1)) - 1;
// The value of dp[i][j][k] is the number
// of subsets of length k having XOR of their
// elements as j from the set arr[0...i-1]
$dp = array(array(array())) ;
// Initializing all the values
// of dp[i][j][k] as 0
for ($i = 0; $i <= $n; $i++)
for ($j = 0; $j <= $m; $j++)
for ($k = 0; $k <= $n; $k++)
$dp[$i][$j][$k] = 0;
// The xor of empty subset is 0
for ($i = 0; $i <= $n; $i++)
$dp[$i][0][0] = 1;
// Fill the dp table
for ($i = 1; $i <= $n; $i++)
{
for ($j = 0; $j <= $m; $j++)
{
for ($k = 0; $k <= $n; $k++)
{
$dp[$i][$j][$k] = $dp[$i - 1][$j][$k];
if ($k != 0)
{
$dp[$i][$j][$k] += $k * $dp[$i - 1][$j ^
$arr[$i - 1]][$k - 1];
}
}
}
}
// The answer is the number of subsets
// of all lengths from set arr[0..n-1]
// having XOR of elements as k
$ans = 0;
for ($i = 1; $i <= $n; $i++)
{
$ans += $dp[$n][$K][$i];
}
return $ans;
}
// Driver Code
$arr = [ 1, 2, 3 ];
$k = 1;
$n = sizeof($arr);
echo subsetXOR($arr, $n, $k);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Returns count of ordered subsets of arr[]
// with XOR value = 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;
// The value of dp[i][j][k] is the number
// of subsets of length k 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][k] 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] = new Array(n + 1);
for (let k = 0; k <= n; k++)
{
dp[i][j][k] = 0;
}
}
}
// The xor of empty subset is 0
for (let i = 0; i <= n; i++)
dp[i][0][0] = 1;
// Fill the dp table
for (let i = 1; i <= n; i++)
{
for (let j = 0; j <= m; j++)
{
for (let k = 0; k <= n; k++)
{
dp[i][j][k] = dp[i - 1][j][k];
if (k != 0)
{
dp[i][j][k] += k * dp[i - 1][j ^
arr[i - 1]][k - 1];
}
}
}
}
// The answer is the number of subsets
// of all lengths from set arr[0..n-1]
// having XOR of elements as k
let ans = 0;
for (let i = 1; i <= n; i++)
{
ans += dp[n][K][i];
}
return ans;
}
let arr = [ 1, 2, 3 ];
let k = 1;
let n = arr.length;
document.write(subsetXOR(arr, n, k));
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por sanskar27jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA