Problem solving with programming: XOR of all sub arrays
Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?
For example let us consider the array [1, 2, 3], all possible sub-arrays are
XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3
And the result XOR[1, 3, 0, 2, 1, 3] = 2.
Efficient Solution:Observe how many times, each element appear in all the sub arrays. In the above example
1 - 3 times
2 - 4 times
3 - 3 times
Consider 0-index, in general A[i] appears (N-i)*(i+1) times.
We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example
V ^ V ^ V ^ V = 0
V ^ V ^ V = V
Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:
N= 2,
A[0] - 2 times
A[1] - 2 times
N = 4,
A[0] - 4 times
A[1] - 6 times
A[2] - 6 times
A[3] - 4 times
This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.
N is odd, the elements at even index will only prevail in the final result.
while(t--)
{
int n;
cin >> n;
int i,j;
int num, result = 0;
for(i = 0; i < n; i++)
{
cin >> num;
if(i % 2 == 0)
result = result ^ num;
}
if(n % 2 == 0) // this check should be called before the loop.
cout << "0" << endl;
else
cout << result << endl;
}
Brute force solution
for i in range(1,N)
for j in range(i,N)
for k in range(i,j)
x = XOR(x,A[k])
Read full article from Problem solving with programming: XOR of all sub arrays
Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?
For example let us consider the array [1, 2, 3], all possible sub-arrays are
XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3
And the result XOR[1, 3, 0, 2, 1, 3] = 2.
Efficient Solution:Observe how many times, each element appear in all the sub arrays. In the above example
1 - 3 times
2 - 4 times
3 - 3 times
Consider 0-index, in general A[i] appears (N-i)*(i+1) times.
We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example
V ^ V ^ V ^ V = 0
V ^ V ^ V = V
Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:
N= 2,
A[0] - 2 times
A[1] - 2 times
N = 4,
A[0] - 4 times
A[1] - 6 times
A[2] - 6 times
A[3] - 4 times
This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.
N is odd, the elements at even index will only prevail in the final result.
while(t--)
{
int n;
cin >> n;
int i,j;
int num, result = 0;
for(i = 0; i < n; i++)
{
cin >> num;
if(i % 2 == 0)
result = result ^ num;
}
if(n % 2 == 0) // this check should be called before the loop.
cout << "0" << endl;
else
cout << result << endl;
}
Brute force solution
for i in range(1,N)
for j in range(i,N)
for k in range(i,j)
x = XOR(x,A[k])
Read full article from Problem solving with programming: XOR of all sub arrays
