Count of all triplets such that XOR of two equals to third element

By Ann Roberts On Mar 14, 2023

Given an array arr[] of positive integers, the task is to find the count of all triplets such that XOR of two equals the third element. In other words count all the triplets (i, j, k) such that
arr[i] ^ arr[j] = arr[k] and i < j < k.

Examples:

Input: arr[] = {1, 2, 3, 4}
Output: 1
Explanation: One such triplet exists in this i.e {1, 2, 3} where 1^2 = 3

Input: arr[] = {1, 2, 3, 4, 3, 2, 1}
Output: 8
Explanation: All the triplets are as follows: {1, 2, 3}, {1, 2, 3}, {1, 3, 2}, {1, 3, 2}, {2, 3, 1}, {2, 3, 1}, {3, 2, 1}, {3, 2, 1}

Approach: This can be solved with the following idea:

In this approach, we iterate through every possible pair(i.e arr[i] and arr[k]) and check if there exists an element in the map that is equal to arr[j] ^ arr[k]. In this map, all the elements between arr[i] and arr[k] will be present along with their frequency at each iteration

The steps involved in this approach are as follows:

Initialize the ‘result‘ variable to 0 and an empty unordered_map ‘m‘. This result variable will store the total count of triplets that satisfy the given condition.
Then we iterate through a nested loop to all the possible pairs of elements in the array(i.e arr[i] and arr[k]).
For each pair of elements arr[i] and arr[k], the program computes their XOR and checks if the XOR exists in an unordered map ‘m'(This map is used to store the frequency of each element in the array present between arr[i] and arr[k])
If the XOR exists in m, it means that there are one or more elements in the array that can be combined with the current pair of elements to form a triplet that satisfies the condition. Then we add the frequency of this third element (which is basically the XOR of the other two) to the variable result.
After checking all possible pairs of elements in the array for a particular index i, the program clears the unordered map m and moves on to the next value of i.
In last we return the count of triplets.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int count_triplet(int arr[], int n)

{

int result = 0;

unordered_map<int, int> m;

for (int i = 0; i < n; i++) {

for (int k = i + 1; k < n; k++) {

int curr_xor = arr[i] ^ arr[k];

if (m.find(curr_xor) != m.end())

result += m[curr_xor];

m[arr[k]]++;

}

m.clear();

}

return result;

}

int main()

{

int arr[] = { 1, 2, 3, 4, 3, 2, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << count_triplet(arr, n);

return 0;

}

Time Complexity: O(N^2)
Auxiliary Space: O(N)