Triplets - 1
Try First, Check Solution later1. 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.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
Check the sample ouput and question video.Question Video
1 <= N <= 1000Sample Input
0 <= arr[i] <= 10^9
1 2 3
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