Number of pairs whose sum is a power of 2 | Set 2 | Java program to implement the above approach ; Function to count all pairs whose sum is power of two ; Stores the frequency of each element of the array ; Update the frequency of array elements ; Stores the count of pairs ; Current power of 2 ; Traverse the array ; Increment count of pairs ; Return count of pairs ; Driver Code
import java . util . * ; class GFG { static int countPair ( int [ ] arr , int n ) { Map < Integer , Integer > m = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) m . put ( arr [ i ] , m . getOrDefault ( arr [ i ] , 0 ) + 1 ) ; int ans = 0 ; for ( int i = 0 ; i < 31 ; i ++ ) { int key = ( int ) Math . pow ( 2 , i ) ; for ( int j = 0 ; j < arr . length ; j ++ ) { int k = key - arr [ j ] ; ans += m . getOrDefault ( k , 0 ) ; if ( k == arr [ j ] ) ans ++ ; } } return ans / 2 ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , - 1 , 2 , 3 } ; int n = arr . length ; System . out . println ( countPair ( arr , n ) ) ; } }