Triplets  1
1. You are given an array(arr) of N numbers.Input Format
2. You have to select three indices i,j,k following this condition >
0 <= i < j <= k < arr.length
3. Two numbers X and Y as defined as :
X = arr[i] ^ arr[i+1] ^ ... ^ arr[j  1]
Y = arr[j] ^ arr[j+1] ^ ... ^ arr[k]
4. You have to print the number of triplets where X is equal to Y.
A number NOutput Format
arr1
arr2..
n numbers
Check the sample ouput and question video.Question Video
1 <= N <= 1000Sample Input
0 <= arr[i] <= 10^9
3Sample Output
1 2 3
2

Editorial
The problem here deals with finding the number of triplets for which X = Y where,
X = arr[i] + arr[i+1] + arr[i+2] + ... + arr[j1] and
Y = arr[j] + arr[j+1] + arr[j+2] + ... + arr[k]
Here 0 <= i < j <= k < arr.length
Consider the following example:
Input array: [ 1, 3, 2, 5, 7, 2, 7, 5, 6, 4 ]
The general approach to solve this problem will be to have 3 nested loops for each i, j, and k and then calculate X and Y and henceforth check for equality. This approach would give us a time complexity of O(n3), but we wish to optimize it to time complexity of O(n2).
The idea behind the optimized approach is to find the subarray where the XOR would be zero. Suppose the subarray with zero XOR is:
[ 2, 3, 3, 2]
This means that 2 ^ 3 ^ 3 ^ 2 = 0
Also 2 = 3 ^ 3 ^ 2.
Also we have, 2 ^ 3 = 3 ^ 2
And lastly, 2 ^ 3 ^ 2 = 3
This depiction is nothing but the positioning of the j variable. Consider placing i at 0th index and k at 3rd index. Now we can have values of index j ranging from 1 <= j <= 3.
So for j = 1, we have X = 2 and Y = 3 ^ 3 ^ 2 => X = Y.
So for j = 2, we have X = 2 ^ 3 and Y = 3 ^ 2 => X = Y.
So for j = 3, we have X = 2 ^ 3 ^ 3 and Y = 2 => X = Y.
So for subarray starting from i till k we can have (ki) triplets satisfying X = Y.
Now coming back to our example, we have I placed at index 2nd and k placed at 7th index so we can directly compute that we can have (72) = 5 triplets satisfying X = Y in this subarray.
So all we need to do is to have a nested looping where we would develop every subarray and then check whether that subarray has a zero result if yes then we would add the number of triplets to our result.
Time Complexity: O(n2)
The time complexity for the function is n2 as we are having a nested loop to generate all subarrays possible.
Space Complexity: O(1)
The space complexity for the function is constant.

Asked in Companies

Related Topics