Xor Equal Triplets

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Adobe

Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the number of triplets (i, j, k), where ‘i’, ‘j’, ‘k’ are three indices of ‘ARR’ such that -:

1. 0 <= ‘i’ < ‘j’ <= ‘k’ < ‘N’ .

2. ARR[i] ^ ARR[i + 1] ^ ... ^ ARR[j - 1] = ARR[j] ^ ARR[j + 1] ^ ... ^ ARR[k] i.e bitwise xor of all integers in subarray of ‘ARR’ between index ‘i’ and ‘j-1’ inclusive, should equals to bitwise xor of all integers in subarray of ‘ARR’ between index ‘j’ and ‘k’ inclusive.

Note:

1. Consider 0 based indexing in ‘ARR’.
2. Symbol ^ denotes the bitwise-xor operation.
3. Xor of subarray having a single integer is that integer itself.
4. It is guaranteed that the number of such triples fit in a 32 bit integer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’, representing the size of ‘ARR’ 

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.
Output Format: 
For each test case, print a single integer that represents the number of such triplets.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 50
2 <= N <= 10000
1 <= ARR[i] <= 2^31 - 1

Time limit: 1 sec
Sample Input 1:
2
2
1 1
5
2 3 1 6 7
Sample Output 1:
1
4
Explanation of sample input 1:
In the first test case, There is one such triplet (0, 1, 1). Note xor of subarray having a single integer is that integer itself.

In the second test case, The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4).
Sample Input 2:
2
5
2 2 2 2 2
2
4 6
Sample Output 2:
10
0
Hint

Try out all possible ways of selecting three indices.

Approaches (3)
Brute Force

The basic idea is to initialize ‘COUNTER’:= 0 and then one by one try out all possible ways of selecting three indices, if for any triplet (i, j, k), Xor of subarray ‘ARR[i:j-1]’ equal Xor of subarray ‘ARR[j:k]’, then increment  ‘COUNTER’ by 1.

 

The steps are as follows:

 

  1. Initialize an integer variable ‘COUNTER’:= 0.
  2. Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
    1. Initialize an integer variable ‘SUBXOR1’: = 0.
    2. Run a loop where ‘j’ ranges from ‘i’+1 to ‘N’-1 and for each ‘j’ do the following -:
      1. Do ‘SUBXOR1’:= ‘SUBXOR1’ ^ ‘ARR[j-1]’, where ^ is bitwise xor operation. Note ‘SUBXOR1’ has xor of all integers of subarray ARR[i:j-1].
      2. Initialize an integer variable ‘SUBXOR2’: = 0.
      3. Run a loop where ‘k’ ranges from ‘j’ to ‘N’-1 and for each ‘k’ do the following -:
        1. Do ‘SUBXOR2’:= ‘SUBXOR2’ ^ ‘ARR[k]’. Note ‘SUBXOR2’ has xor of all integers of subarray ‘ARR[j:k]’.
        2. If  ‘SUBXOR1’ =  ‘SUBXOR1’, then increment ‘COUNTER’ by 1.
  3. Return ‘COUNTER’.
Time Complexity

O(N^3), where 'N' is the size of ‘ARR’.

 

There are three nested loops each run at most ‘N’ times. Thus, the overall time complexity will be O(N^3). 

Space Complexity

O(1)

 

We are using constant extra space here.

Code Solution
(100% EXP penalty)
Xor Equal Triplets
Full screen
Console