Рубрики

Подсчитать количество подмножеств, имеющих конкретное значение XOR

Для данного массива arr [] из n чисел и числа K найдите количество подмножеств arr [], имеющих XOR элементов в виде K

Примеры :

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}

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Подход грубой силы O (2 n ): Один наивный подход состоит в том, чтобы сгенерировать все 2 n подмножеств и подсчитать все подмножества, имеющие значение XOR K, но этот подход не будет эффективным для больших значений n.

Подход динамического программирования O (n * m):
Мы определяем число m таким образом, что m = pow (2, (log2 (max (arr)) + 1)) — 1. Это число на самом деле является максимальным значением, которое может получить любое подмножество XOR. Мы получаем это число, считая биты в наибольшем числе. Мы создаем двумерный массив dp [n + 1] [m + 1], такой, что dp [i] [j] равен числу подмножеств, имеющих значение XOR j из подмножеств arr [0… i-1] .

Заполняем массив dp следующим образом:

  1. Мы инициализируем все значения dp [i] [j] как 0.
  2. Установите значение dp [0] [0] = 1, поскольку XOR пустого набора равно 0.
  3. Переберите все значения arr [i] слева направо и для каждого arr [i], переберите все возможные значения XOR, то есть от 0 до m (оба включительно), и заполните массив dp следующим образом:
    для i = 1 до n:
    для j = 0 до m:
    dp [i] [j] = dp [i-1] [j] + dp [i-1] [j ^ arr [i-1]]
    Это можно объяснить следующим образом: если существует подмножество arr [0… i-2] со значением XOR j, то также существует подмножество arr [0… i-1] со значением XOR j. также, если существует подмножество arr [0… .i-2] со значением XOR j ^ arr [i], тогда, очевидно, существует подмножество arr [0… i-1] со значением XOR j, как j ^ arr [i- 1] ^ arr [i-1] = j.
  4. Подсчет количества подмножеств со значением XOR k: поскольку dp [i] [j] — это число подмножеств, имеющих j в качестве значения XOR из подмножеств arr [0..i-1], то количество подмножеств из набора arr [0..n] со значением XOR в качестве K будет dp [n] [K]

C / C ++

// arr динамическое программирование решения для поиска номера
// подмножеств, имеющих xor их элементов как k
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество подмножеств arr [] со значением XOR, равным
// к.

int subsetXOR(int arr[], int n, int k)

{

    // Найти максимальный элемент в arr []

    int max_ele = arr[0];

    for (int i=1; i<n; i++)

       if (arr[i] > max_ele)

           max_ele = arr[i];

  

    // Максимально возможное значение XOR

    int m = (1 << (int)(log2(max_ele) + 1) ) - 1;

  

    // Значение dp [i] [j] - это количество подмножеств, имеющих

    // XOR их элементов как j из множества arr [0 ... i-1]

    int dp[n+1][m+1];

  

    // Инициализируем все значения dp [i] [j] как 0

    for (int i=0; i<=n; i++)

        for (int j=0; j<=m; j++)

            dp[i][j] = 0;

  

    // Xor пустого подмножества равно 0

    dp[0][0] = 1;

  

    // Заполняем таблицу дп

    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]];

  

    // Ответ - номер подмножества из множества

    // arr [0..n-1] с XOR элементов в качестве k

    return dp[n][k];

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

}

python3

# Python 3 arr решение для динамического программирования
# для определения количества подмножеств, имеющих
# xor их элементов как k

import math

  
# Возвращает количество подмножеств arr [] с
# Значение XOR равно k.

def subsetXOR(arr, n, k):

      

    # Найти максимальный элемент в arr []

    max_ele = arr[0]

    for i in range(1, n):

        if arr[i] > max_ele :

            max_ele = arr[i]

              

    # Максимально возможное значение XOR

    m = (1 << (int)(math.log2(max_ele) + 1)) - 1

      

    # Значение dp [i] [j] - это число

    # подмножеств, имеющих XOR своих элементов

    # как j из набора arr [0 ... i-1]

  

    # Инициализация всех значений

    # дп [я] [j] как 0

    dp = [[0 for i in range(m + 1)]

             for i in range(n + 1)]

      

    # Xor пустого подмножества равно 0

    dp[0][0] = 1

  

    # Заполните таблицу дп

    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]])

  

    # Ответ номер подмножества

    # из набора arr [0..n-1], имеющего XOR

    # элементов как k

    return dp[n][k]

  
Код водителя

arr = [1, 2, 3, 4, 5]

k = 4

n = len(arr)

print("Count of subsets is"

       subsetXOR(arr, n, k))

  
# Этот код добавлен
# от sahishelangia

C #

// C # динамическое программирование решения для поиска номера
// подмножеств, имеющих xor их элементов как k

using System;

  

class GFG

{

      
// Возвращает количество подмножеств arr [] с
// Значение XOR равно k.

static int subsetXOR(int []arr, int n, int k)

{

    // Найти максимальный элемент в arr []

    int max_ele = arr[0];

    for (int i = 1; i < n; i++)

    if (arr[i] > max_ele)

        max_ele = arr[i];

  

    // Максимально возможное значение XOR

    int m = (1 << (int)(Math.Log(max_ele,2) + 1) ) - 1;

  

    // Значение dp [i] [j] - это количество подмножеств, имеющих

    // XOR их элементов как j из множества arr [0 ... i-1]

    int [,]dp=new int[n+1,m+1];

  

    // Инициализируем все значения dp [i] [j] как 0

    for (int i = 0; i <= n; i++)

        for (int j = 0; j <= m; j++)

            dp[i, j] = 0;

  

    // Xor пустого подмножества равно 0

    dp[0, 0] = 1;

  

    // Заполняем таблицу дп

    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]];

  

    // Ответ - номер подмножества из множества

    // arr [0..n-1] с XOR элементов в качестве k

    return dp[n, k];

}

  

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен jit_t.

PHP

<?php
// PHP arr динамическое программирование
// решение для поиска номера
// подмножеств, имеющих xor их
// элементы как k

  
// Возвращает количество подмножеств
// arr [] со значением XOR, равным k.

function subsetXOR($arr, $n, $k)

{

    // Найти максимальный элемент в arr []

    $max_ele = $arr[0];

    for ($i = 1; $i < $n; $i++)

    if ($arr[$i] > $max_ele)

        $max_ele = $arr[$i];

  

    // Максимально возможное значение XOR

    $m = (1 << (int)(log($max_ele

                    2) + 1) ) - 1;

  

    // Значение dp [i] [j] является

    // количество подмножеств, имеющих

    // XOR их элементов как j

    // из набора arr [0 ... i-1]

      

    // Инициализация всех

    // значения dp [i] [j] как 0

    for ($i = 0; $i <= $n; $i++)

        for ($j = 0; $j <= $m; $j++)

            $dp[$i][$j] = 0;

  

    // Xor пустого подмножества равно 0

    $dp[0][0] = 1;

  

    // Заполняем таблицу дп

    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]];

  

    // Ответ номер

    // подмножества из множества arr [0..n-1]

    // имеющий XOR элементов в качестве k

    return $dp[$n][$k];

}

  
// Код драйвера

$arr = array (1, 2, 3, 4, 5);

$k = 4;

$n = sizeof($arr);

echo "Count of subsets is "

     subsetXOR($arr, $n, $k);

  
// Этот код предоставлен ajit
?>


Выход :

Count of subsets is 4

Эта статья предоставлена Pranay Pandey . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитать количество подмножеств, имеющих конкретное значение XOR

0.00 (0%) 0 votes