Number of pairs whose sum is a power of 2 | Java 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
import java . util . TreeMap ; class Count { static int countPairs ( int [ ] a , int n ) { TreeMap < Integer , Integer > map = new TreeMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { map . put ( a [ i ] , 1 ) ; } int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( map . get ( 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 . get ( a [ i ] ) == 1 ) continue ; count ++ ; map . put ( cur - a [ i ] , map . get ( cur - a [ i ] ) - 1 ) ; map . put ( a [ i ] , map . get ( a [ i ] ) - 1 ) ; } } return count ; } public static void main ( String [ ] args ) { int [ ] a = { 3 , 11 , 14 , 5 , 13 } ; int n = a . length ; System . out . println ( countPairs ( a , n ) ) ; } }