Question : Find the Bitwise XOR of the value of all sub arrays of array A.
Input : A = [1,2] Output : 0 Explanation : Sub Arrays :[1], [2], [1,2] (XOR of all subarrays = 0)
Solution:
To find XOR of all sub arrays (consecutive element of array), we have to find whether a element of array appears in an odd or an even number of subarrays. It the count of subarray is odd, it will appear in the xor sum, and if its even it won’t. The element at position i will be included in (i+1) * (N-i) subarrays. That’s because any subarray that includes i can starts at index 0, 1, …, i. and ends at index i, i+1, …, N-1 i.e. total number of start index for sub array including i is (i+1), and end index is (N -1 - i + 1). So frequency of element at ith index is given by (i+1)*(N-i) where N is size of array.
Basically we have to consider all the set of Power Set. A power set can be found using binary representation if we write down the sequence of binary numbers (using n digits), and then let “1” mean “put the matching member into this subset”. For set {a, b, c}, power set using binary representation is given by
| abc | Subset | |
|---|---|---|
| 0 | 000 | { } |
| 1 | 001 | {c} |
| 2 | 010 | {b} |
| 3 | 011 | {b,c} |
| 4 | 100 | {a} |
| 5 | 101 | {a,c} |
| 6 | 110 | {a,b} |
| 7 | 111 | {a,b,c} |
Now coming back to the problem, there are 4 cases possible based on value of i and N i.e.
- Case 1: i is odd, N is odd
Let i = 2k+1, N = 2m+1 frequency[i] = ((2k+1)+1)*((2m+1)-(2k+1)) = 4(m-k)(k+1) = even
- Case 2: i is odd, N is even
Let i = 2k+1, N = 2m frequency[i] = ((2k+1)+1)*((2m)-(2k+1)) = 2(k+1)(2m-2k-1) = even
- Case 3: i is even, N is odd
Let i = 2k, N = 2m+1 frequency [i] = ((2k)+1)*((2m+1)-(2k)) = 2k(2m-2k+1)+(2m-2k)+1 = odd
- Case 4: i is even, N is even
Let i = 2k, N = 2m freq[i] = ((2k)+1)*((2m)-(2k)) = 2(m-k)(2k+1) = even
From this, we can conclude that if total no.of elements in the array is even, then frequency of element at any position is even. So total XOR will be 0. And if total no. of elements are odd, then frequency of elements at even positions are odd and odd positions are even. So we need to find only the XOR of elements at even positions.