Find sum of xor of all unordered triplets of the array | Java program to find sum of xor of all unordered triplets of the array ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Returns n ^ ( - 1 ) mod p ; Returns nCr % p using Fermat 's little theorem. ; Base case ; Fill factorial array so that we can find all factorial of r , n and n - r ; Function returns sum of xor of all unordered triplets of the array ; Iterating over the bits ; Number of elements whith k 'th bit  1 and 0 respectively ; Checking if k 'th bit is 1 ; Adding this bit 's part to the answer ; Driver code
class GFG { static int power ( int x , int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( ( y & 1 ) == 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } static int modInverse ( int n , int p ) { return power ( n , p - 2 , p ) ; } static int nCrModPFermat ( int n , int r , int p ) { if ( r == 0 ) return 1 ; if ( n < r ) return 0 ; int fac [ ] = new int [ n + 1 ] ; fac [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) fac [ i ] = fac [ i - 1 ] * i % p ; return ( fac [ n ] * modInverse ( fac [ r ] , p ) % p * modInverse ( fac [ n - r ] , p ) % p ) % p ; } static int SumOfXor ( int a [ ] , int n ) { int mod = 10037 ; int answer = 0 ; for ( int k = 0 ; k < 32 ; k ++ ) { int x = 0 , y = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ( a [ i ] & ( 1 << k ) ) != 0 ) x ++ ; else y ++ ; } answer += ( ( 1 << k ) % mod * ( nCrModPFermat ( x , 3 , mod ) + x * nCrModPFermat ( y , 2 , mod ) ) % mod ) % mod ; } return answer ; } public static void main ( String [ ] args ) { int n = 5 ; int A [ ] = { 3 , 5 , 2 , 18 , 7 } ; System . out . println ( SumOfXor ( A , n ) ) ; } }