Number of pairs whose sum is a power of 2 | Set 2 | Python3 program to implement the above approach ; Function to count all pairs whose sum is a power of two ; Stores the frequency of each element of the array ; Update frequency of array elements ; Stores count of required pairs ; Current power of 2 ; Traverse the array ; If pair does not exist ; Increment count of pairs ; Return the count of pairs ; Driver Code
from math import pow NEW_LINE def countPair ( arr , n ) : NEW_LINE INDENT m = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ arr [ i ] ] = m . get ( arr [ i ] , 0 ) + 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 31 ) : NEW_LINE INDENT key = int ( pow ( 2 , i ) ) NEW_LINE for j in range ( n ) : NEW_LINE INDENT k = key - arr [ j ] NEW_LINE if k not in m : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT ans += m . get ( k , 0 ) NEW_LINE DEDENT if ( k == arr [ j ] ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT DEDENT return ans // 2 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 8 , 2 , 10 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countPair ( arr , n ) ) NEW_LINE DEDENT