Número de elementos que no pueden formar ningún par cuya suma sea potencia de 2

Dada una array arr[] de longitud N , la tarea es imprimir el número de elementos de la array que no pueden formar un par con ningún otro elemento de la array cuya suma sea una potencia de dos.
Ejemplos: 

Entrada: arr[] = {6, 2, 11} 
Salida: 1 
Explicación: 
Dado que 6 y 2 pueden formar un par con suma 8 (= 2 ³ ). Por lo tanto, solo se debe eliminar 11, ya que no forma una suma que sea una potencia de 2. 
Entrada: arr[] = [1, 1, 1, 1023], 
Salida: 0 
Explicación: 
Los elementos de array dados se pueden dividir en siguientes dos pares: 
(1, 1) con suma 2 (= 2 ¹ ) 
(1, 1023) con suma 1024 (= 2 ¹⁰ ) 
Por lo tanto, no es necesario eliminar ningún elemento. 
 

Enfoque: 
Para resolver el problema mencionado anteriormente, siga los pasos a continuación: 

• Almacene las frecuencias de todos los elementos de la array en un mapa .
• Para cada elemento del arreglo a[i], itere sobre todas las sumas posibles p = {2 ⁰ , 2 ¹ , …., 2 ³⁰ } y verifique si p – a[i] está presente en el arreglo o no.
• Cualquiera de las dos condiciones siguientes debe cumplirse: 
  1. Sea s = p – a[i]. Si s está presente en el arreglo más de una vez, entonces es posible un par consistente en a[i] con suma p.
  2. Si s está presente solo una vez en el arreglo, entonces s tiene que ser diferente de a[i] para un posible par.
  3. Si ninguna de las dos condiciones anteriores se cumple, ningún par que consista en a[i] es posible con suma p.
• Si las dos condiciones anteriores no se cumplen para ningún p para el a[i] actual, entonces aumente el conteo ya que a[i] no puede formar una suma que sea una potencia de 2 con ningún otro elemento de la array.
• Imprime el valor final de count .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to count of
// array elements which do
// not form a pair with sum
// equal to a power of 2
// with any other array element
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// and return the
// count of elements
 
int powerOfTwo(int a[], int n)
{
    // Stores the frequencies
    // of every array element
 
    map<int, int> mp;
 
    for (int i = 0; i < n; i++)
        mp[a[i]]++;
 
    // Stores the count
    // of removals
 
    int count = 0;
 
    for (int i = 0; i < n; i++) {
        bool f = false;
 
        // For every element, check if
        // it can form a sum equal to
        // any power of 2 with any other
        // element
 
        for (int j = 0; j < 31; j++) {
 
            // Store pow(2, j) - a[i]
            int s = (1 << j) - a[i];
 
            // Check if s is present
            // in the array
            if (mp.count(s)
 
                // If frequency of s
                // exceeds 1
                && (mp[s] > 1
 
                    // If s has frequency 1
                    // but is different from
                    // a[i]
                    || mp[s] == 1 && s != a[i]))
 
                // Pair possible
                f = true;
        }
 
        // If no pair possible for
        // the current element
 
        if (f == false)
            count++;
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
int main()
{
    int a[] = { 6, 2, 11 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << powerOfTwo(a, n);
 
    return 0;
}

// Java program to count of array
// elements which do not form a
// pair with sum equal to a power
// of 2 with any other array element
import java.util.*;
 
class GFG{
 
// Function to calculate and return
// the count of elements
static int powerOfTwo(int a[], int n)
{
     
    // Stores the frequencies
    // of every array element
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
 
    for(int i = 0; i < n; i++)
    {
       if(mp.containsKey(a[i]))
       {
           mp.put(a[i], mp.get(a[i]) + 1);
       }
       else
       {
           mp.put(a[i], 1);
       }
    }
     
    // Stores the count
    // of removals
    int count = 0;
 
    for(int i = 0; i < n; i++)
    {
       boolean f = false;
        
       // For every element, check if
       // it can form a sum equal to
       // any power of 2 with any other
       // element
       for(int j = 0; j < 31; j++)
       {
           
          // Store Math.pow(2, j) - a[i]
          int s = (1 << j) - a[i];
           
          // Check if s is present
          // in the array
          if (mp.containsKey(s) &&
              
             // If frequency of s
             // exceeds 1
             (mp.get(s) > 1 ||
              
              // If s has frequency 1
              // but is different from
              // a[i]
              mp.get(s) == 1 && s != a[i]))
              
             // Pair possible
             f = true;
       }
        
       // If no pair possible for
       // the current element
       if (f == false)
           count++;
    }
     
    // Return the answer
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 6, 2, 11 };
    int n = a.length;
     
    System.out.print(powerOfTwo(a, n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to count of
# array elements which do
# not form a pair with sum
# equal to a power of 2
# with any other array element
from collections import defaultdict
 
# Function to calculate
# and return the
# count of elements
def powerOfTwo(a, n):
 
    # Stores the frequencies
    # of every array element
    mp = defaultdict (int)
 
    for i in range (n):
        mp[a[i]] += 1
 
    # Stores the count
    # of removals
    count = 0
 
    for i in range (n):
        f = False
 
        # For every element, check if
        # it can form a sum equal to
        # any power of 2 with any other
        # element
 
        for j in range (31):
 
            # Store pow(2, j) - a[i]
            s = (1 << j) - a[i]
 
            # Check if s is present
            # in the array
            if (s in mp
 
                # If frequency of s
                # exceeds 1
                and (mp[s] > 1
 
                    # If s has frequency 1
                    # but is different from
                    # a[i]
                    or mp[s] == 1 and
                       s != a[i])):
 
                # Pair possible
                f = True
 
        # If no pair possible for
        # the current element
        if (f == False):
            count += 1
   
    # Return the answer
    return count
 
# Driver Code
if __name__ == "__main__":
   
    a = [6, 2, 11]
    n = len(a)
    print(powerOfTwo(a, n))
 
# This code is contributed by Chitranayal

// C# program to count of array
// elements which do not form a
// pair with sum equal to a power
// of 2 with any other array element
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate and return
// the count of elements
static int powerOfTwo(int []a, int n)
{
     
    // Stores the frequencies
    // of every array element
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
 
    for(int i = 0; i < n; i++)
    {
        if(mp.ContainsKey(a[i]))
        {
            mp[a[i]] = mp[a[i]] + 1;
        }
        else
        {
            mp.Add(a[i], 1);
        }
    }
     
    // Stores the count
    // of removals
    int count = 0;
 
    for(int i = 0; i < n; i++)
    {
        bool f = false;
         
        // For every element, check if
        // it can form a sum equal to
        // any power of 2 with any other
        // element
        for(int j = 0; j < 31; j++)
        {
         
            // Store Math.Pow(2, j) - a[i]
            int s = (1 << j) - a[i];
             
            // Check if s is present
            // in the array
            if (mp.ContainsKey(s) &&
                 
                // If frequency of s
                // exceeds 1
                (mp[s] > 1 ||
                 
                // If s has frequency 1
                // but is different from
                // a[i]
                mp[s] == 1 && s != a[i]))
                 
                // Pair possible
                f = true;
        }
         
        // If no pair possible for
        // the current element
        if (f == false)
            count++;
    }
     
    // Return the answer
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = { 6, 2, 11 };
    int n = a.Length;
     
    Console.Write(powerOfTwo(a, n));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program to count of array
// elements which do not form a
// pair with sum equal to a power
// of 2 with any other array element
 
// Function to calculate and return
// the count of elements
function powerOfTwo(a, n)
{
      
    // Stores the frequencies
    // of every array element
    let mp = new Map();
  
    for(let i = 0; i < n; i++)
    {
       if(mp.has(a[i]))
       {
           mp.set(a[i], mp.get(a[i]) + 1);
       }
       else
       {
           mp.set(a[i], 1);
       }
    }
      
    // Stores the count
    // of removals
    let count = 0;
  
    for(let i = 0; i < n; i++)
    {
       let f = false;
         
       // For every element, check if
       // it can form a sum equal to
       // any power of 2 with any other
       // element
       for(let j = 0; j < 31; j++)
       {
            
          // Store Math.pow(2, j) - a[i]
          let s = (1 << j) - a[i];
            
          // Check if s is present
          // in the array
          if (mp.has(s) &&
               
             // If frequency of s
             // exceeds 1
             (mp.get(s) > 1 ||
               
              // If s has frequency 1
              // but is different from
              // a[i]
              mp.get(s) == 1 && s != a[i]))
               
             // Pair possible
             f = true;
       }
         
       // If no pair possible for
       // the current element
       if (f == false)
           count++;
    }
      
    // Return the answer
    return count;
}
 
// Driver code
 
    let a = [ 6, 2, 11 ];
    let n = a.length;
      
    document.write(powerOfTwo(a, n));
  
 // This code is contributed by sourabhghosh0416.
</script>

1

Complejidad de tiempo: O(N*log(N)) 
Espacio auxiliar: O(N)