Número mínimo de elementos que deben eliminarse para que la array sea buena

Dada una array arr[] , la tarea es encontrar la cantidad mínima de elementos que deben eliminarse para que la array sea buena. Una secuencia a ₁ , a ₂ … an se _dice buena si para cada elemento a _i existe un elemento a _j (i no es igual a j) tal que a _i + a _j es una potencia de dos, es decir, 2 ^d para algún entero no negativo d. Ejemplos:
 
 

Entrada: arr[] = {4, 7, 1, 5, 4, 9} 
Salida: 1 
Elimine 5 de la array para que la array sea buena.
Entrada: arr[] = {1, 3, 1, 1} 
Salida: 0 
 

Enfoque: Deberíamos eliminar solo una _i para la cual no hay una _j (i no es igual a j) tal que _ai + _aj sea una potencia de 2. 
Para cada valor, encontremos el número de sus ocurrencias en la array. Podemos usar la estructura de datos del mapa .
Ahora podemos comprobar fácilmente que a _i no tiene un par a _j . Iteremos sobre todas las sumas posibles, S = 2 ⁰ , 2 ¹ , …, 2 ³⁰ y para cada S calculemos S – a[i] si existe en el mapa.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number
// of elements that must be removed
// to make the given array good
int minimumRemoval(int n, int a[])
{
 
    map<int, int> c;
 
    // Count frequency of each element
    for (int i = 0; i < n; i++)
        c[a[i]]++;
 
    int ans = 0;
 
    // For each element check if there
    // exists another element that makes
    // a valid pair
    for (int i = 0; i < n; i++) {
        bool ok = false;
        for (int j = 0; j < 31; j++) {
            int x = (1 << j) - a[i];
            if (c.count(x) && (c[x] > 1
                       || (c[x] == 1 && x != a[i]))) {
                ok = true;
                break;
            }
        }
 
        // If does not exist then
        // increment answer
        if (!ok)
            ans++;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 4, 7, 1, 5, 4, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minimumRemoval(n, a);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the minimum number
// of elements that must be removed
// to make the given array good
static int minimumRemoval(int n, int a[])
{
 
    Map<Integer,Integer> c = new HashMap<>();
 
    // Count frequency of each element
    for (int i = 0; i < n; i++)
        if(c.containsKey(a[i]))
        {
            c.put(a[i], c.get(a[i])+1);
        }
        else
        {
            c.put(a[i], 1);
        }
 
    int ans = 0;
 
    // For each element check if there
    // exists another element that makes
    // a valid pair
    for (int i = 0; i < n; i++)
    {
        boolean ok = false;
        for (int j = 0; j < 31; j++)
        {
            int x = (1 << j) - a[i];
            if ((c.get(x) != null && (c.get(x) > 1)) ||
                c.get(x) != null && (c.get(x) == 1 && x != a[i]))
            {
                ok = true;
                break;
            }
        }
 
        // If does not exist then
        // increment answer
        if (!ok)
            ans++;
    }
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 4, 7, 1, 5, 4, 9 };
    int n = a.length;
    System.out.println(minimumRemoval(n, a));
}
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the approach
 
# Function to return the minimum number
# of elements that must be removed
# to make the given array good
def minimumRemoval(n, a) :
 
    c = dict.fromkeys(a, 0);
 
    # Count frequency of each element
    for i in range(n) :
        c[a[i]] += 1;
 
    ans = 0;
 
    # For each element check if there
    # exists another element that makes
    # a valid pair
    for i in range(n) :
        ok = False;
        for j in range(31) :
             
            x = (1 << j) - a[i];
            if (x in c and (c[x] > 1 or
               (c[x] == 1 and x != a[i]))) :
                 
                ok = True;
                break;
 
        # If does not exist then
        # increment answer
        if (not ok) :
            ans += 1;
             
    return ans;
 
# Driver Code
if __name__ == "__main__" :
     
    a = [ 4, 7, 1, 5, 4, 9 ];
    n = len(a) ;
     
    print(minimumRemoval(n, a));
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System.Linq;
using System;
 
class GFG
{
// Function to return the minimum number
// of elements that must be removed
// to make the given array good
static int minimumRemoval(int n, int []a)
{
 
    int[] c = new int[1000];
 
    // Count frequency of each element
    for (int i = 0; i < n; i++)
        c[a[i]]++;
 
    int ans = 0;
 
    // For each element check if there
    // exists another element that makes
    // a valid pair
    for (int i = 0; i < n; i++)
    {
        bool ok = true;
        for (int j = 0; j < 31; j++)
        {
            int x = (1 << j) - a[i];
            if (c.Contains(x) && (c[x] > 1 ||
                    (c[x] == 1 && x != a[i])))
            {
                ok = false;
                break;
            }
        }
 
        // If does not exist then
        // increment answer
        if (!ok)
            ans++;
    }
 
    return ans;
}
 
// Driver code
static void Main()
{
    int []a = { 4, 7, 1, 5, 4, 9 };
    int n = a.Length;
    Console.WriteLine(minimumRemoval(n, a));
}
}
 
// This code is contributed by mits

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum number
// of elements that must be removed
// to make the given array good
function minimumRemoval( n, a)
{
 
    var c = {};
 
    // Count frequency of each element
    for (let i = 0; i < n; i++){
        if(a[i] in c)
          c[a[i]]++;
        else
          c[a[i]] = 1;
    }
 
    var ans = 0;
 
    // For each element check if there
    // exists another element that makes
    // a valid pair
    for (let i = 0; i < n; i++) {
        var ok = false;
        for (let j = 0; j < 31; j++) {
            let x = (1 << j) - a[i];
           
            if ((x in c && c[x] > 1)
                       || (c[x] == 1 && x != a[i])) {
                         
                ok = true;
                break;
            }
        }
 
        // If does not exist then
        // increment answer
        if (!ok)
            ans++;
    }
 
    return ans;
}
 
// Driver code
var a = new Array( 4, 7, 1, 5, 4, 9 );
var n = a.length;
console.log(minimumRemoval(n, a));
 
// This code is contributed by ukasp.   
</script>

1

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar: O(n)