Number of triplets in array having subarray xor equal | Java trie based program to find the Number of triplets in array having subarray xor equal ; maximum number of bits in an integer <= 1e9 ; Structure of a Trie Node ; [ 0 ] index is bit 0 and [ 1 ] index is bit 1 ; Sum of indexes inserted at at a node ; Number of indexes inserted at a node ; Constructor to initialize a newly created node ; Function to insert curr_xor into the trie ; Iterate from the 31 st bit to the 0 th bit of curr_xor number ; Check if the current bit is set or not ; If this node isn 't already  present in the trie structure  insert it into the trie. ; Increase the sum of indexes by the current index value ; Increase the number of indexes by 1 ; Function to check if curr_xor is present in trie or not ; Iterate from the 31 st bit to the 0 th bit of curr_xor number ; Check if the current bit is set or not ; 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 ; Calculate the number of index inserted at final node ; Calculate the sum of index inserted at final node ; Function to return the count of valid triplets ; To store cumulative xor ; The root of the trie ; Insert the curr_xor in the trie ; Update the cumulative xor ; Check if the cumulative xor is present in the trie or not if present then add ( sz * index ) - sum ; Driver Code ; Given array
class GFG { static int lg = 31 ; static class TrieNode { TrieNode children [ ] ; int sum_of_indexes ; int number_of_indexes ; TrieNode ( ) { children = new TrieNode [ 2 ] ; this . children [ 0 ] = null ; this . children [ 1 ] = null ; this . sum_of_indexes = 0 ; this . number_of_indexes = 0 ; } } ; static void insert ( TrieNode node , int num , int index ) { for ( int bits = lg ; bits >= 0 ; bits -- ) { int curr_bit = ( num >> bits ) & 1 ; if ( node . children [ curr_bit ] == null ) { node . children [ curr_bit ] = new TrieNode ( ) ; } node = node . children [ curr_bit ] ; } node . sum_of_indexes += index ; node . number_of_indexes ++ ; } static int query ( TrieNode node , int num , int index ) { for ( int bits = lg ; bits >= 0 ; bits -- ) { int curr_bit = ( num >> bits ) & 1 ; if ( node . children [ curr_bit ] == null ) { return 0 ; } node = node . children [ curr_bit ] ; } int sz = node . number_of_indexes ; int sum = node . sum_of_indexes ; int ans = ( sz * index ) - ( sum ) ; return ans ; } static int no_of_triplets ( int arr [ ] , int n ) { int curr_xor = 0 ; int number_of_triplets = 0 ; TrieNode root = new TrieNode ( ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = arr [ i ] ; insert ( root , curr_xor , i ) ; curr_xor ^= x ; number_of_triplets += query ( root , curr_xor , i ) ; } return number_of_triplets ; } public static void main ( String args [ ] ) { int arr [ ] = { 5 , 2 , 7 } ; int n = arr . length ; System . out . println ( no_of_triplets ( arr , n ) ) ; } }