Question

Divide array into equal parts such that xor is equal

Answer 1

Explanation:

Let’s denote XOR between all elements in the first group as G1 and XOR between all elements in the second group as G2. Now, the following relation is always correct: G1 ⊕ G2 = A1 ⊕ A2 ⊕ …. ⊕ An.

So for G1 = G2, xor between all elements of array A is equal to 0. So, in that case, answer will be (2n – 2)/2 = (2n-1 – 1). In second case, when XOR between all elements isn’t 0, we can not split array. Answer will be 0.

// CPP Program to count number of ways to split

// array into two groups such that each group

// has equal XOR value

#include<bits/stdc++.h>

using namespace std;

// Return the count number of ways to split

// array into two groups such that each group

// has equal XOR value.

int countgroup(int a[], int n)

{

int xs = 0;

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

xs = xs ^ a[i];

// We can split only if XOR is 0. Since

// XOR of all is 0, we can consider all

// subsets as one group.

if (xs == 0)

return (1 << (n-1)) - 1;

return 0;

}

// Driver Program

int main()

{

int a[] = { 1, 2, 3 };

int n = sizeof(a)/sizeof(a[0]);

cout << countgroup(a, n) << endl;

return 0;

}