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.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.
Input Format
A number N
arr1
arr2..
n numbers
Output Format
Check the sample ouput and question video.
Question Video
Constraints
1 <= N <= 1000
0 <= arr[i] <= 10^9
Sample Input
3
1 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.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name