Number of pairs whose sum is a power of 2 | Set 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPair ( int arr [ ] , int n ) { map < int , int > m ; for ( int i = 0 ; i < n ; i ++ ) m [ arr [ i ] ] ++ ; int ans = 0 ; for ( int i = 0 ; i < 31 ; i ++ ) { int key = pow ( 2 , i ) ; for ( int j = 0 ; j < n ; j ++ ) { int k = key - arr [ j ] ; if ( m . find ( k ) == m . end ( ) ) continue ; else ans += m [ k ] ; if ( k == arr [ j ] ) ans ++ ; } } return ans / 2 ; } int main ( ) { int arr [ ] = { 1 , 8 , 2 , 10 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countPair ( arr , n ) << endl ; return 0 ; }