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 ; 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
using System ; using System . Collections . Generic ; class GFG { static int countPairs ( int [ ] a , int n ) { Dictionary < int , int > map = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! map . ContainsKey ( a [ i ] ) ) map . Add ( a [ i ] , 1 ) ; } int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( map [ a [ i ] ] < 1 ) continue ; int cur = 1 ; while ( cur <= a [ i ] ) cur <<= 1 ; if ( map . ContainsKey ( cur - a [ i ] ) ) { if ( cur - a [ i ] == a [ i ] && map [ a [ i ] ] == 1 ) continue ; count ++ ; map [ cur - a [ i ] ] = map [ cur - a [ i ] ] - 1 ; map [ a [ i ] ] = map [ a [ i ] ] - 1 ; } } return count ; } public static void Main ( String [ ] args ) { int [ ] a = { 3 , 11 , 14 , 5 , 13 } ; int n = a . Length ; Console . WriteLine ( countPairs ( a , n ) ) ; } }