Number of pairs whose sum is a power of 2 | C ++ implementation of above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairs ( int a [ ] , int n ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) mp [ a [ i ] ] ++ ; sort ( a , a + n , greater < int > ( ) ) ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp [ a [ i ] ] < 1 ) continue ; int cur = 1 ; while ( cur <= a [ i ] ) cur <<= 1 ; if ( mp [ cur - a [ i ] ] ) { if ( cur - a [ i ] == a [ i ] and mp [ a [ i ] ] == 1 ) continue ; count ++ ; mp [ cur - a [ i ] ] -- ; mp [ a [ i ] ] -- ; } } return count ; } int main ( ) { int a [ ] = { 3 , 11 , 14 , 5 , 13 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << countPairs ( a , n ) ; return 0 ; }