Find triplets in an array whose AND is maximum | Python3 program to find triplet with maximum bitwise AND . ; Flag Array initially set to true for all numbers ; 2D array for bit representation of all the numbers . Initially all bits are set to 0. ; Finding bit representation of every number and storing it in bits array . ; Checking last bit of the number ; Dividing number by 2. ; maximum And number initially 0. ; Traversing the 2d binary representation . 0 th index represents 32 th bits while 32 th index represents 0 th bit . ; If cnt greater than 3 then ( 32 - i ) th bits of the number will be set . ; Setting flags of the numbers whose ith bit is not set . ; Counting the numbers whose flag are true . ; Driver Code
def maxTriplet ( a , n ) : NEW_LINE INDENT f = [ True for i in range ( n ) ] NEW_LINE bits = [ [ 0 for i in range ( 33 ) ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT num = a [ i ] NEW_LINE j = 32 NEW_LINE while ( num ) : NEW_LINE INDENT if ( num & 1 ) : NEW_LINE INDENT bits [ i ] [ j ] = 1 NEW_LINE DEDENT j -= 1 NEW_LINE num >>= 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 33 ) : NEW_LINE INDENT cnt = 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( bits [ j ] [ i ] and f [ j ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT if ( cnt >= 3 ) : NEW_LINE INDENT ans += pow ( 2 , 32 - i ) NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( bits [ j ] [ i ] == False ) : NEW_LINE INDENT f [ j ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( f [ i ] ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT NumberOfTriplets = ( cnt * ( cnt - 1 ) * ( cnt - 2 ) ) // 6 NEW_LINE print ( NumberOfTriplets , ans ) NEW_LINE DEDENT a = [ 4 , 11 , 10 , 15 , 26 ] NEW_LINE n = len ( a ) NEW_LINE maxTriplet ( a , n ) NEW_LINE