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 = 3Input: 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++
// C++ Implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to count tripletsint count_triplet(int arr[], int n){ // Variable to count result int result = 0; // Create empty map unordered_map<int, int> m; // Loop through all possible // pairs of elements for (int i = 0; i < n; i++) { for (int k = i + 1; k < n; k++) { // Compute XOR of current pair int curr_xor = arr[i] ^ arr[k]; // If XOR exists in map then // add its frequency to result if (m.find(curr_xor) != m.end()) result += m[curr_xor]; // Increment count of // current element m[arr[k]]++; } // Clear the unordered_map m.clear(); } // Return total count of triplets return result;}// Driver programint main(){ int arr[] = { 1, 2, 3, 4, 3, 2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << count_triplet(arr, n); return 0;} |
Java
// Java Implementation of the above approachimport java.util.HashMap;public class Main { // Function to count triplets static int count_triplet(int arr[], int n) { // Variable to count result int result = 0; // Create empty map HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Loop through all possible // pairs of elements for (int i = 0; i < n; i++) { for (int k = i + 1; k < n; k++) { // Compute XOR of current pair int curr_xor = arr[i] ^ arr[k]; // If XOR exists in map then // add its frequency to result if (m.containsKey(curr_xor)) { result += m.get(curr_xor); } // Increment count of // current element m.put(arr[k], m.getOrDefault(arr[k], 0) + 1); } // Clear the map m.clear(); } // Return total count of triplets return result; } // Driver program public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 3, 2, 1 }; int n = arr.length; // Function call System.out.println(count_triplet(arr, n)); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python Implementation of the above approach# Function to count tripletsdef count_triplet(arr, n): # Variable to count result result = 0 # Create empty dictionary m = {} # Loop through all possible # pairs of elements for i in range(n): for k in range(i + 1, n): # Compute XOR of current pair curr_xor = arr[i] ^ arr[k] # If XOR exists in dictionary then # add its frequency to result if curr_xor in m: result += m[curr_xor] # Increment count of current element if arr[k] in m: m[arr[k]] += 1 else: m[arr[k]] = 1 # Clear the dictionary m.clear() # Return total count of triplets return result# Driver programarr = [1, 2, 3, 4, 3, 2, 1]n = len(arr)# Function callprint(count_triplet(arr, n)) |
C#
using System;using System.Collections.Generic;class GFG { static int count_triplet(int[] arr, int n) { int result = 0; Dictionary<int, int> m = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { for (int k = i + 1; k < n; k++) { int curr_xor = arr[i] ^ arr[k]; if (m.ContainsKey(curr_xor)) { result += m[curr_xor]; } if (m.ContainsKey(arr[k])) { m[arr[k]]++; } else { m[arr[k]] = 1; } } m.Clear(); } return result; } static void Main() { int[] arr = { 1, 2, 3, 4, 3, 2, 1 }; int n = arr.Length; Console.WriteLine(count_triplet(arr, n)); }} |
Javascript
// Function to count tripletsfunction count_triplet(arr, n) { // Variable to count result let result = 0; // Create empty map let m = new Map(); // Loop through all possible pairs of elements for (let i = 0; i < n; i++) { for (let k = i + 1; k < n; k++) { // Compute XOR of current pair let curr_xor = arr[i] ^ arr[k]; // If XOR exists in map then add its frequency to result if (m.has(curr_xor)) { result += m.get(curr_xor); } // Increment count of current element if (m.has(arr[k])) { m.set(arr[k], m.get(arr[k]) + 1); } else { m.set(arr[k], 1); } } // Clear the map m.clear(); } // Return total count of triplets return result;}// Driver programlet arr = [1, 2, 3, 4, 3, 2, 1];let n = arr.length;// Function callconsole.log(count_triplet(arr, n)); |
Output
8
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
