Given an array arr[] of N non-negative integers. The task is to count the number of triplets (i, j, k) where 0 ? i < j ? k < N such that A[i] ^ A[i + 1] ^ … ^ A[j – 1] = A[j] ^ A[j + 1] ^ … ^ A[k] where ^ is the bitwise XOR.
Examples:
Input: arr[] = {2, 5, 6, 4, 2}
Output: 2
The valid triplets are (2, 3, 4) and (2, 4, 4).
Input: arr[] = {5, 2, 7}
Output: 2
Naive approach: Consider each and every triplet and check whether the xor of the required elements is equal or not.
Efficient approach: If arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = arr[j] ^ arr[j + 1] ^ … ^ arr[k] then arr[i] ^ arr[i + 1] ^ … ^ arr[k] = 0 since X ^ X = 0. Now the problem gets reduced to finding the sub-arrays with XOR 0. But every such sub-array can have multiple such triplets i.e.
If arr[i] ^ arr[i + 1] ^ … ^ arr[k] = 0
then, (arr[i]) ^ (arr[i + 1] ^ … ^ arr[k]) = 0
and, arr[i] ^ (arr[i + 1]) ^ … ^ arr[k] = 0
arr[i] ^ arr[i + 1] ^ (arr[i + 2]) ^ … ^ arr[k] = 0
…
j can have any value from i + 1 to k without violating the required property.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required tripletsint CountTriplets(int* arr, int n){ int ans = 0; for (int i = 0; i < n - 1; i++) { // First element of the // current sub-array int first = arr[i]; for (int j = i + 1; j < n; j++) { // XOR every element of // the current sub-array first ^= arr[j]; // If the XOR becomes 0 then // update the count of triplets if (first == 0) ans += (j - i); } } return ans;}// Driver codeint main(){ int arr[] = { 2, 5, 6, 4, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << CountTriplets(arr, n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count// of required tripletsstatic int CountTriplets(int[] arr, int n){ int ans = 0; for (int i = 0; i < n - 1; i++) { // First element of the // current sub-array int first = arr[i]; for (int j = i + 1; j < n; j++) { // XOR every element of // the current sub-array first ^= arr[j]; // If the XOR becomes 0 then // update the count of triplets if (first == 0) ans += (j - i); } } return ans;}// Driver codepublic static void main(String[] args){ int arr[] = {2, 5, 6, 4, 2}; int n = arr.length; System.out.println(CountTriplets(arr, n));}} // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach# Function to return the count# of required tripletsdef CountTriplets(arr, n): ans = 0 for i in range(n - 1): # First element of the # current sub-array first = arr[i] for j in range(i + 1, n): # XOR every element of # the current sub-array first ^= arr[j] # If the XOR becomes 0 then # update the count of triplets if (first == 0): ans += (j - i) return ans# Driver codearr = [2, 5, 6, 4, 2 ]n = len(arr)print(CountTriplets(arr, n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the count // of required triplets static int CountTriplets(int[] arr, int n) { int ans = 0; for (int i = 0; i < n - 1; i++) { // First element of the // current sub-array int first = arr[i]; for (int j = i + 1; j < n; j++) { // XOR every element of // the current sub-array first ^= arr[j]; // If the XOR becomes 0 then // update the count of triplets if (first == 0) ans += (j - i); } } return ans; } // Driver code public static void Main() { int []arr = {2, 5, 6, 4, 2}; int n = arr.Length; Console.WriteLine(CountTriplets(arr, n)); }}// This code is contributed by AnkitRai01 |
Javascript
// Function to return the count// of required tripletsfunction CountTriplets(arr, n) { let ans = 0; for (let i = 0; i < n - 1; i++) { // First element of the current sub-array let first = arr[i]; for (let j = i + 1; j < n; j++) { // XOR every element of the current sub-array first ^= arr[j]; // If the XOR becomes 0 then update the count of triplets if (first == 0) ans += j - i; } } return ans;}// Driver codeconst arr = [2, 5, 6, 4, 2];const n = arr.length;console.log(CountTriplets(arr, n)); |
2
Time Complexity: O(n2).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
