Number of pairs whose sum is a power of 2 | Function to return the count of valid pairs ; Storing occurrences of each element ; Sort the array in deceasing order ; Start taking largest element each time ; If element has already been paired ; Find the number which is greater than a [ i ] and power of two ; If there is a number which adds up with a [ i ] to form a power of two ; Edge case when a [ i ] and crr - a [ i ] is same and we have only one occurrence of a [ i ] then it cannot be paired ; Remove already paired elements ; Return the count ; Driver code
def countPairs ( a , n ) : NEW_LINE INDENT mp = dict . fromkeys ( a , 0 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT mp [ a [ i ] ] += 1 NEW_LINE DEDENT a . sort ( reverse = True ) NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( mp [ a [ i ] ] < 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT cur = 1 NEW_LINE while ( cur <= a [ i ] ) : NEW_LINE INDENT cur = cur << 1 NEW_LINE DEDENT if ( cur - a [ i ] in mp . keys ( ) ) : NEW_LINE INDENT if ( cur - a [ i ] == a [ i ] and mp [ a [ i ] ] == 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT count += 1 NEW_LINE mp [ cur - a [ i ] ] -= 1 NEW_LINE mp [ a [ i ] ] -= 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 3 , 11 , 14 , 5 , 13 ] NEW_LINE n = len ( a ) NEW_LINE print ( countPairs ( a , n ) ) NEW_LINE DEDENT