# Triplets - 1

#### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given an array(arr) of N numbers.2. You have to select three indices i,j,k following this condition ->       0 <= i < j <= k < arr.length3. 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.`
Input Format
`A number Narr1arr2..n numbers`
Output Format
`Check the sample ouput and question video.`
Question Video
Constraints
`1 <= N <= 10000 <= arr[i] <= 10^9`
Sample Input
`31 2 3`
Sample Output
`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[j-1] 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 sub-array where the XOR would be zero. Suppose the sub-array 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 sub-array starting from i till k we can have (k-i) 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 (7-2) = 5 triplets satisfying X = Y in this sub-array.

So all we need to do is to have a nested looping where we would develop every sub-array and then check whether that sub-array 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 sub-arrays possible.

Space Complexity: O(1)

The space complexity for the function is constant.

• Related Topics

Run

Run
Id Name