Count pairs made up of an element divisible by the other from an array consisting of powers of 2 | Function to count the number of pairs as per the given conditions ; Initialize array set_bits as 0 ; Store the total number of required pairs ; Traverse the array arr [ ] ; Store arr [ i ] in x ; Store the position of the leftmost set bit in arr [ i ] ; Increase bit position ; Divide by 2 to shift bits in right at each step ; Count of pairs for index i till its set bit position ; Increasing count of set bit position of current elelement ; Prthe answer ; Driver Code ; Function Call
def numberOfPairs ( arr , N ) : NEW_LINE INDENT set_bits = [ 0 ] * 31 NEW_LINE count = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT x = arr [ i ] NEW_LINE bitpos = - 1 NEW_LINE while ( x > 0 ) : NEW_LINE INDENT bitpos += 1 NEW_LINE x //= 2 NEW_LINE DEDENT for j in range ( bitpos + 1 ) : NEW_LINE INDENT count += set_bits [ j ] NEW_LINE DEDENT set_bits [ bitpos ] += 1 NEW_LINE DEDENT print ( count ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 16 , 8 , 64 ] NEW_LINE N = len ( arr ) NEW_LINE numberOfPairs ( arr , N ) NEW_LINE DEDENT