Number of triplets in array having subarray xor equal
Given an array of integers Arr. The task is to count the number of triplets (i, j, k) such that Ai ^ Ai+1 ^ Ai+2 ^ …. ^ Aj-1 = Aj ^ Aj+1 ^ Aj+2 ^ ….. ^ Ak, and 0 ?i< j? k < N, where N is the size of the array.
Where ^ is the bitwise xor of two numbers.
Examples:
Input: Arr = {5, 2, 7}
Output: 2
The triplets are (0, 2, 2) since 5 ^ 2 = 7 and (0, 1, 2) since 2 ^ 7 = 5.Input: Arr = {1, 2, 3, 4, 5}
Output: 5
Brute force Approach: A simple solution is to run three nested loops iterating through all possible values of i, j and k and then another loop to calculate the xor of both the first and second subarray.
The time complexity of this solution is O(N4).
C++
// A simple C++ program to find Number of triplets // in array having subarray xor equal #include <bits/stdc++.h> using namespace std; // Function to return the count int xor_triplet( int arr[], int n) { // Initialise result int ans = 0; // Pick 1st element of the triplet for ( int i = 0; i < n; i++) { // Pick 2nd element of the triplet for ( int j = i + 1; j < n; j++) { // Pick 3rd element of the triplet for ( int k = j; k < n; k++) { int xor1 = 0, xor2 = 0; // Taking xor in the // first subarray for ( int x = i; x < j; x++) { xor1 ^= arr[x]; } // Taking xor in the // second subarray for ( int x = j; x <= k; x++) { xor2 ^= arr[x]; } // If both xor is equal if (xor1 == xor2) { ans++; } } } } return ans; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); // Function Calling cout << xor_triplet(arr, n); return 0; } |
Java
// Java program to find Number of triplets // in array having subarray xor equal class GFG { // Function to return the count static int xor_triplet( int arr[], int n) { // Initialise result int ans = 0 ; // Pick 1st element of the triplet for ( int i = 0 ; i < n; i++) { // Pick 2nd element of the triplet for ( int j = i + 1 ; j < n; j++) { // Pick 3rd element of the triplet for ( int k = j; k < n; k++) { int xor1 = 0 , xor2 = 0 ; // Taking xor in the // first subarray for ( int x = i; x < j; x++) { xor1 ^= arr[x]; } // Taking xor in the // second subarray for ( int x = j; x <= k; x++) { xor2 ^= arr[x]; } // If both xor is equal if (xor1 == xor2) { ans++; } } } } return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int n = arr.length; // Function Calling System.out.println(xor_triplet(arr, n)); } } // This code is contributed by AnkitRai01 |
Python3
# A simple python3 program to find Number of triplets # in array having subarray xor equal # Function to return the count def xor_triplet(arr, n): # Initialise result ans = 0 # Pick 1st element of the triplet for i in range (n): # Pick 2nd element of the triplet for j in range (i + 1 , n): # Pick 3rd element of the triplet for k in range (j, n): xor1 = 0 xor2 = 0 # Taking xor in the # first subarray for x in range (i, j): xor1 ^ = arr[x] # Taking xor in the # second subarray for x in range (j, k + 1 ): xor2 ^ = arr[x] # If both xor is equal if (xor1 = = xor2): ans + = 1 return ans # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 ] n = len (arr) # Function Calling print (xor_triplet(arr, n)) # This code is contributed by PrinciRaj1992 |
C#
// C# program to find Number of triplets // in array having subarray xor equal using System; class GFG { // Function to return the count static int xor_triplet( int [] arr, int n) { // Initialise result int ans = 0; // Pick 1st element of the triplet for ( int i = 0; i < n; i++) { // Pick 2nd element of the triplet for ( int j = i + 1; j < n; j++) { // Pick 3rd element of the triplet for ( int k = j; k < n; k++) { int xor1 = 0, xor2 = 0; // Taking xor in the // first subarray for ( int x = i; x < j; x++) { xor1 ^= arr[x]; } // Taking xor in the // second subarray for ( int x = j; x <= k; x++) { xor2 ^= arr[x]; } // If both xor is equal if (xor1 == xor2) { ans++; } } } } return ans; } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; // Function Calling Console.WriteLine(xor_triplet(arr, n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // A simple Javascript program to find Number of triplets // in array having subarray xor equal // Function to return the count function xor_triplet(arr, n) { // Initialise result let ans = 0; // Pick 1st element of the triplet for (let i = 0; i < n; i++) { // Pick 2nd element of the triplet for (let j = i + 1; j < n; j++) { // Pick 3rd element of the triplet for (let k = j; k < n; k++) { let xor1 = 0, xor2 = 0; // Taking xor in the // first subarray for (let x = i; x < j; x++) { xor1 ^= arr[x]; } // Taking xor in the // second subarray for (let x = j; x <= k; x++) { xor2 ^= arr[x]; } // If both xor is equal if (xor1 == xor2) { ans++; } } } } return ans; } // Driver Code let arr = [1, 2, 3, 4, 5]; let n = arr.length; // Function Calling document.write(xor_triplet(arr, n)) // This code is contributed by _saurabh_jaiswal </script> |
5
Time Complexity: O(N4)
Auxiliary Space: O(1)
Better Approach:
- A better approach is to use Prefix Xor
- Let, a = A[i] ^ A[i + 1] ^ … ^ A[j – 1]
b = A[j] ^ A[j + 1] ^ … ^ A[k] - Assume a == b, thus
a ^ a = b ^ a, thus
0 = b ^ a, thus
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] ^ arr[j] ^ arr[j + 1] ^ … ^ arr[k] = 0
prefix[k+1] = prefix[i] - We only need to find out how many pair (i, k) of prefix value are equal. So we can calculate the prefix array first, then brute force count the pair.
- Because we once we determine the pair (i,k), j can be any number that i < j <= k, so we need to plus k – i – 1 to the result res.
Below is the implementation of the above approach:
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static int no_of_triplets( int arr[], int n) { n=n+ 1 ; int res = 0 , prefix[] = new int [n]; //prefix xor of the array for ( int i = 1 ; i < n; ++i) prefix[i] = arr[i - 1 ] ^ prefix[i - 1 ]; for ( int i = 0 ; i < n; ++i) for ( int j = i + 1 ; j < n; ++j) //counting many pair have prefix value are equal. if (prefix[i] == prefix[j]) res += j - i - 1 ; return res; } //Drivers Code public static void main (String[] args) { int arr[]={ 5 , 2 , 7 }; int n=arr.length; System.out.println(no_of_triplets(arr,n)); } } //This code is contributed by Utkarsh Raj Mishra |
Python
# python code for approach class GFG: @staticmethod def no_of_triplets(arr, n): n = n + 1 res = 0 prefix = [ 0 ] * n # prefix xor of the array for i in range ( 1 , n): prefix[i] = arr[i - 1 ] ^ prefix[i - 1 ] for i in range (n): for j in range (i + 1 , n): # counting many pair have prefix value are # equal. if prefix[i] = = prefix[j]: res + = j - i - 1 return res # Driver Code if __name__ = = "__main__" : arr = [ 5 , 2 , 7 ] n = len (arr) print (GFG.no_of_triplets(arr, n)) # This code is generated by Chetan Bargal |
C#
// C# code with comments using System; class GFG { public static int no_of_triplets( int [] arr, int n) { n = n + 1; int res = 0; int [] prefix = new int [n]; // prefix xor of the array for ( int i = 1; i < n; ++i) prefix[i] = arr[i - 1] ^ prefix[i - 1]; for ( int i = 0; i < n; ++i) for ( int j = i + 1; j < n; ++j) // counting many pair have prefix value are // equal. if (prefix[i] == prefix[j]) res += j - i - 1; return res; } // Driver Code static void Main( string [] args) { int [] arr = { 5, 2, 7 }; int n = arr.Length; Console.WriteLine(no_of_triplets(arr, n)); } } // This code is contributed by phasing17 |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the number // of triplets int no_of_triplets( int arr[], int n) { n = n + 1; int res = 0, prefix[n]; // Prefix xor of the array for ( int i = 1; i < n; ++i) prefix[i] = arr[i - 1] ^ prefix[i - 1]; for ( int i = 0; i < n; ++i) for ( int j = i + 1; j < n; ++j) // Counting how many pairs have // the same prefix value if (prefix[i] == prefix[j]) res += j - i - 1; return res; } // Driver Code int main() { int arr[] = { 5, 2, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << no_of_triplets(arr, n); return 0; } |
Javascript
function no_of_triplets(arr, n) { n = n + 1; let res = 0, prefix = new Array(n); // prefix XOR of the array prefix[0] = 0; for (let i = 1; i < n; ++i) { prefix[i] = arr[i - 1] ^ prefix[i - 1]; } for (let i = 0; i < n; ++i) { for (let j = i + 1; j < n; ++j) { // counting how many pairs have the same prefix value if (prefix[i] == prefix[j]) { res += j - i - 1; } } } return res; } // Drivers Code let arr = [5, 2, 7]; let n = arr.length; console.log(no_of_triplets(arr, n)); |
2
Time complexity: O(N2)
Auxiliary Space: O(N).
Efficient Approach:
- An efficient solution is to use Trie.
- One observation is that if the subarray from i to k have Ai ^ Ai+1 ^ …. ^ Ak = 0 then we can select any j such that i < j <= k and that will always satisfy our condition.
- This observation will be used to calculate the number of triplets.
- We will take the cumulative xor of the elements in the array and check that this xor value exists in the Trie or not.
- If the xor already exists in the Trie then we have encountered a subarray having 0 xor and count all the triplets.
- Else push the value of xor into the Trie.
Below is the implementation of the above approach:
C++
// C++ trie based program to find the Number of // triplets in array having subarray xor equal #include <bits/stdc++.h> using namespace std; // maximum number of bits // in an integer <= 1e9 #define lg 31 // Structure of a Trie Node struct TrieNode { // [0] index is bit 0 // and [1] index is bit 1 TrieNode* children[2]; // Sum of indexes // inserted at a node int sum_of_indexes; // Number of indexes // inserted at a node int number_of_indexes; // Constructor to initialize // a newly created node TrieNode() { this ->children[0] = nullptr; this ->children[1] = nullptr; this ->sum_of_indexes = 0; this ->number_of_indexes = 0; } }; // Function to insert curr_xor // into the trie void insert(TrieNode* node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor // number for ( int bits = lg; bits >= 0; bits--) { // Check if the current // bit is set or not int curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // insert it into the trie. if (node->children[curr_bit] == nullptr) { node->children[curr_bit] = new TrieNode(); } node = node->children[curr_bit]; } // Increase the sum of // indexes by the current // index value node->sum_of_indexes += index; // Increase the number // of indexes by 1 node->number_of_indexes++; } // Function to check if curr_xor // is present in trie or not int query(TrieNode* node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor number for ( int bits = lg; bits >= 0; bits--) { // Check if the current bit // is set or not int curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // that means no sub array till // current index has 0 xor so // return 0 if (node->children[curr_bit] == nullptr) { return 0; } node = node->children[curr_bit]; } // Calculate the number of index // inserted at final node int sz = node->number_of_indexes; // Calculate the sum of index // inserted at final node int sum = node->sum_of_indexes; int ans = (sz * index) - (sum); return ans; } // Function to return the count of // valid triplets int no_of_triplets( int arr[], int n) { // To store cumulative xor int curr_xor = 0; int number_of_triplets = 0; // The root of the trie TrieNode* root = new TrieNode(); for ( int i = 0; i < n; i++) { int x = arr[i]; // Insert the curr_xor in the trie insert(root, curr_xor, i); // Update the cumulative xor curr_xor ^= x; // Check if the cumulative xor // is present in the trie or not // if present then add // (sz * index) - sum number_of_triplets += query(root, curr_xor, i); } return number_of_triplets; } // Driver Code int main() { // Given array int arr[] = { 5, 2, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << no_of_triplets(arr, n); return 0; } |
Java
// Java trie based program to find the Number of // triplets in array having subarray xor equal class GFG { // maximum number of bits // in an integer <= 1e9 static int lg = 31 ; // Structure of a Trie Node static class TrieNode { // [0] index is bit 0 // and [1] index is bit 1 TrieNode children[]; // Sum of indexes // inserted at at a node int sum_of_indexes; // Number of indexes // inserted at a node int number_of_indexes; // Constructor to initialize // a newly created node TrieNode() { children = new TrieNode[ 2 ]; this .children[ 0 ] = null ; this .children[ 1 ] = null ; this .sum_of_indexes = 0 ; this .number_of_indexes = 0 ; } }; // Function to insert curr_xor // into the trie static void insert(TrieNode node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor // number for ( int bits = lg; bits >= 0 ; bits--) { // Check if the current // bit is set or not int curr_bit = (num >> bits) & 1 ; // If this node isn't already // present in the trie structure // insert it into the trie. if (node.children[curr_bit] == null ) { node.children[curr_bit] = new TrieNode(); } node = node.children[curr_bit]; } // Increase the sum of // indexes by the current // index value node.sum_of_indexes += index; // Increase the number // of indexes by 1 node.number_of_indexes++; } // Function to check if curr_xor // is present in trie or not static int query(TrieNode node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor number for ( int bits = lg; bits >= 0 ; bits--) { // Check if the current bit // is set or not int curr_bit = (num >> bits) & 1 ; // If this node isn't already // present in the trie structure // that means no sub array till // current index has 0 xor so // return 0 if (node.children[curr_bit] == null ) { return 0 ; } node = node.children[curr_bit]; } // Calculate the number of index // inserted at final node int sz = node.number_of_indexes; // Calculate the sum of index // inserted at final node int sum = node.sum_of_indexes; int ans = (sz * index) - (sum); return ans; } // Function to return the count of // valid triplets static int no_of_triplets( int arr[], int n) { // To store cumulative xor int curr_xor = 0 ; int number_of_triplets = 0 ; // The root of the trie TrieNode root = new TrieNode(); for ( int i = 0 ; i < n; i++) { int x = arr[i]; // Insert the curr_xor in the trie insert(root, curr_xor, i); // Update the cumulative xor curr_xor ^= x; // Check if the cumulative xor // is present in the trie or not // if present then add // (sz * index) - sum number_of_triplets += query(root, curr_xor, i); } return number_of_triplets; } // Driver Code public static void main(String args[]) { // Given array int arr[] = { 5 , 2 , 7 }; int n = arr.length; System.out.println(no_of_triplets(arr, n)); } } // This code is contributed by Arnab Kundu |
Python3
# Python 3 trie based program to find the Number of # triplets in array having subarray xor equal class GFG : # maximum number of bits # in an integer <= 1e9 lg = 31 # Structure of a Trie Node class TrieNode : # [0] index is bit 0 # and [1] index is bit 1 children = None # Sum of indexes # inserted at at a node sum_of_indexes = 0 # Number of indexes # inserted at a node number_of_indexes = 0 # Constructor to initialize # a newly created node def __init__( self ) : self .children = [ None ] * ( 2 ) self .children[ 0 ] = None self .children[ 1 ] = None self .sum_of_indexes = 0 self .number_of_indexes = 0 # Function to insert curr_xor # into the trie @staticmethod def insert( node, num, index) : # Iterate from the 31st bit # to the 0th bit of curr_xor # number bits = GFG.lg while (bits > = 0 ) : # Check if the current # bit is set or not curr_bit = (num >> bits) & 1 # If this node isn't already # present in the trie structure # insert it into the trie. if (node.children[curr_bit] = = None ) : node.children[curr_bit] = GFG.TrieNode() node = node.children[curr_bit] bits - = 1 # Increase the sum of # indexes by the current # index value node.sum_of_indexes + = index # Increase the number # of indexes by 1 node.number_of_indexes + = 1 # Function to check if curr_xor # is present in trie or not @staticmethod def query( node, num, index) : # Iterate from the 31st bit # to the 0th bit of curr_xor number bits = GFG.lg while (bits > = 0 ) : # Check if the current bit # is set or not curr_bit = (num >> bits) & 1 # If this node isn't already # present in the trie structure # that means no sub array till # current index has 0 xor so # return 0 if (node.children[curr_bit] = = None ) : return 0 node = node.children[curr_bit] bits - = 1 # Calculate the number of index # inserted at final node sz = node.number_of_indexes # Calculate the sum of index # inserted at final node sum = node.sum_of_indexes ans = (sz * index) - ( sum ) return ans # Function to return the count of # valid triplets @staticmethod def no_of_triplets( arr, n) : # To store cumulative xor curr_xor = 0 number_of_triplets = 0 # The root of the trie root = GFG.TrieNode() i = 0 while (i < n) : x = arr[i] # Insert the curr_xor in the trie GFG.insert(root, curr_xor, i) # Update the cumulative xor curr_xor ^ = x # Check if the cumulative xor # is present in the trie or not # if present then add # (sz * index) - sum number_of_triplets + = GFG.query(root, curr_xor, i) i + = 1 return number_of_triplets # Driver Code @staticmethod def main( args) : # Given array arr = [ 5 , 2 , 7 ] n = len (arr) print (GFG.no_of_triplets(arr, n)) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# trie based program to find the Number of // triplets in array having subarray xor equal using System; // Structure of a Trie Node class TrieNode { // [0] index is bit 0 // and [1] index is bit 1 public TrieNode[] children; // Sum of indexes // inserted at at a node public int sum_of_indexes; // Number of indexes // inserted at a node public int number_of_indexes; // Constructor to initialize // a newly created node public TrieNode() { children = new TrieNode[2]; this .children[0] = null ; this .children[1] = null ; this .sum_of_indexes = 0; this .number_of_indexes = 0; } } public class GFG { // maximum number of bits // in an integer <= 1e9 static int lg = 31; // Function to insert curr_xor // into the trie static void insert(TrieNode node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor // number for ( int bits = lg; bits >= 0; bits--) { // Check if the current // bit is set or not int curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // insert it into the trie. if (node.children[curr_bit] == null ) { node.children[curr_bit] = new TrieNode(); } node = node.children[curr_bit]; } // Increase the sum of // indexes by the current // index value node.sum_of_indexes += index; // Increase the number // of indexes by 1 node.number_of_indexes++; } // Function to check if curr_xor // is present in trie or not static int query(TrieNode node, int num, int index) { // Iterate from the 31st bit // to the 0th bit of curr_xor number for ( int bits = lg; bits >= 0; bits--) { // Check if the current bit // is set or not int curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // that means no sub array till // current index has 0 xor so // return 0 if (node.children[curr_bit] == null ) { return 0; } node = node.children[curr_bit]; } // Calculate the number of index // inserted at final node int sz = node.number_of_indexes; // Calculate the sum of index // inserted at final node int sum = node.sum_of_indexes; int ans = (sz * index) - (sum); return ans; } // Function to return the count of // valid triplets static int no_of_triplets( int [] arr, int n) { // To store cumulative xor int curr_xor = 0; int number_of_triplets = 0; // The root of the trie TrieNode root = new TrieNode(); for ( int i = 0; i < n; i++) { int x = arr[i]; // Insert the curr_xor in the trie insert(root, curr_xor, i); // Update the cumulative xor curr_xor ^= x; // Check if the cumulative xor // is present in the trie or not // if present then add // (sz * index) - sum number_of_triplets += query(root, curr_xor, i); } return number_of_triplets; } static public void Main() { // Given array int [] arr = { 5, 2, 7 }; int n = arr.Length; Console.WriteLine(no_of_triplets(arr, n)); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript trie based program to find the Number of // triplets in array having subarray xor equal // maximum number of bits // in an integer <= 1e9 const lg = 31; // Structure of a Trie Node class TrieNode { constructor() { // [0] index is bit 0 // and [1] index is bit 1 this .children = [ null , null ]; // Sum of indexes // inserted at a node this .sum_of_indexes = 0; // Number of indexes // inserted at a node this .number_of_indexes = 0; } } // Function to insert curr_xor // into the trie const insert = (node, num, index) => { // Iterate from the 31st bit // to the 0th bit of curr_xor // number for (let bits = lg; bits >= 0; bits--) { // Check if the current // bit is set or not const curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // insert it into the trie. if (node.children[curr_bit] == null ) { node.children[curr_bit] = new TrieNode(); } node = node.children[curr_bit]; } // Increase the sum of // indexes by the current // index value node.sum_of_indexes += index; // Increase the number // of indexes by 1 node.number_of_indexes++; }; // Function to check if curr_xor // is present in trie or not const query = (node, num, index) => { // Iterate from the 31st bit // to the 0th bit of curr_xor number for (let bits = lg; bits >= 0; bits--) { // Check if the current bit // is set or not const curr_bit = (num >> bits) & 1; // If this node isn't already // present in the trie structure // that means no sub array till // current index has 0 xor so // return 0 if (node.children[curr_bit] == null ) { return 0; } node = node.children[curr_bit]; } // Calculate the number of index // inserted at final node const sz = node.number_of_indexes; // Calculate the sum of index // inserted at final node const sum = node.sum_of_indexes; const ans = (sz * index) - (sum); return ans; }; // Function to return the count of // valid triplets const no_of_triplets = (arr, n) => { // To store cumulative xor let curr_xor = 0; let number_of_triplets = 0; // The root of the trie const root = new TrieNode(); for (let i = 0; i < n; i++) { const x = arr[i]; // Insert the curr_xor in the trie insert(root, curr_xor, i); // Update the cumulative xor curr_xor ^= x; // Check if the cumulative xor // is present in the trie or not // if present then add // (sz * index) - sum number_of_triplets += query(root, curr_xor, i); } return number_of_triplets; }; // Driver Code // Given array const arr = [5, 2, 7]; const n = arr.length; console.log(no_of_triplets(arr, n)); // contributed by akashish__ |
2
Time complexity: O(31*N)
Auxiliary Space: O(N).