For a given sequence of positive integers A1,A2,…,AN, you are supposed to find the number of triplets (i,j,k) such that Ai^Ai+1^..^Aj-1=Aj^Aj+1^..Ak where ^ denotes bitwise XOR. The link to the question is here: https://www.codechef.com/AUG19B/problems/KS1 All I did is try to find all subarrays with xor 0. The solution works but is quadratic time and thus too slow. This is the solution that I managed to get to.
for (int i = 0; i < arr.length; i++) {
int xor = arr[i];
for (int j = i + 1; j < arr.length; j++) {
xor ^= arr[j];
if (xor == 0) {
ans += (j - i);
}
}
}
finAns.append(ans + "\n");
Here's an
O(n)
solution based on CiaPan's comment under the question description:The function
f
is the main method.brute_force
is used for validation.Python 2.7 code: