Count of elements which cannot form any pair whose sum is power of 2 | Python3 program to count of array elements which do not form a pair with sum equal to a power of 2 with any other array element ; Function to calculate and return the count of elements ; Stores the frequencies of every array element ; Stores the count of removals ; For every element , check if it can form a sum equal to any power of 2 with any other element ; Store pow ( 2 , j ) - a [ i ] ; Check if s is present in the array ; If frequency of s exceeds 1 ; If s has frequency 1 but is different from a [ i ] ; Pair possible ; If no pair possible for the current element ; Return the answer ; Driver Code
from collections import defaultdict NEW_LINE def powerOfTwo ( a , n ) : NEW_LINE INDENT mp = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT mp [ a [ i ] ] += 1 NEW_LINE DEDENT count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT f = False NEW_LINE for j in range ( 31 ) : NEW_LINE INDENT s = ( 1 << j ) - a [ i ] NEW_LINE if ( s in mp and ( mp [ s ] > 1 or mp [ s ] == 1 and s != a [ i ] ) ) : NEW_LINE INDENT f = True NEW_LINE DEDENT DEDENT if ( f == False ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 6 , 2 , 11 ] NEW_LINE n = len ( a ) NEW_LINE print ( powerOfTwo ( a , n ) ) NEW_LINE DEDENT