Sum of Bitwise AND of all unordered triplets of an array | Function to calculate sum of Bitwise AND of all unordered triplets from a given array such that ( i < j < k ) ; Stores the resultant sum of Bitwise AND of all triplets ; Traverse over all the bits ; Count number of elements with the current bit set ; There are ( cnt ) C ( 3 ) numbers with the current bit set and each triplet contributes 2 ^ bit to the result ; Return the resultant sum ; Driver Code
def tripletAndSum ( arr , n ) : NEW_LINE INDENT ans = 0 NEW_LINE for bit in range ( 32 ) : NEW_LINE INDENT cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] & ( 1 << bit ) ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT ans += ( 1 << bit ) * cnt * ( cnt - 1 ) * ( cnt - 2 ) // 6 NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 3 , 5 , 4 , 7 ] NEW_LINE N = len ( arr ) NEW_LINE print ( tripletAndSum ( arr , N ) ) NEW_LINE