Count distinct possible Bitwise XOR values of subsets of an array

  

#include <bits/stdc++.h>

using namespace std;

  

unordered_set<int> s;

  

void countXOR(int arr[], int comb[],

              int start, int end,

              int index, int r)

{

    

    

    if (index == r) {

  

        

        

        int new_xor = 0;

  

        

        for (int j = 0; j < r; j++) {

            new_xor ^= comb[j];

        }

  

        

        

        s.insert(new_xor);

        return;

    }

  

    

    

    for (int i = start;

         i <= end && end - i + 1 >= r - index; i++) {

        comb[index] = arr[i];

  

        

        countXOR(arr, comb, i + 1, end,

                 index + 1, r);

    }

}

  

void maxSizeSet(int arr[], int N)

{

    

    for (int r = 2; r <= N; r++) {

        int comb[r + 1];

  

        

        countXOR(arr, comb, 0, N - 1,

                 0, r);

    }

  

    

    cout << s.size() << endl;

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    maxSizeSet(arr, N);

  

    return 0;

}

Let's block ads! (Why?)