Eliminaciones mínimas que se realizarán en una array dada, de modo que la suma de cada par sea una potencia de 2

Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de elementos que deben eliminarse, de modo que por cada elemento restante arr[i] , exista otro elemento arr[j], (i!=j ) tal que la suma de arr[i] y arr[j] es una potencia de 2 . Si después de cualquier cantidad de eliminaciones, no existe tal par, imprima -1.

Ejemplos:

Entrada: arr[]={1, 2, 3, 4, 5, 6}, N = 6
Salida: 1
Explicación: 
Quitar 4 es suficiente ya que, para los elementos restantes existe un elemento tal que su suma es una potencia de 2:

  1. Para 1, existe 3 tal que (1+3=4) es una potencia de 2.
  2. Para 2, existe 6 tal que (2+6=8) es una potencia de 2.
  3. Para 3, existe 1 tal que (3+1=4) es una potencia de 2.
  4. Para 5, existe 3 tal que (5+3=8) es una potencia de 2.
  5. Para 6, existe 2 tal que (6+2=8) es una potencia de 2.

Entrada: A={1, 5, 10, 25, 50}, N=5
Salida: -1

Enfoque: La idea es utilizar operadores bit a bit y el mapa para realizar un seguimiento de las frecuencias de cada elemento. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable ans a 0 para almacenar la cantidad de elementos que se eliminarán.
  • Calcule la frecuencia de todos los elementos en arr[] y guárdelos en un mapa , digamos mp .
  • Iterar de 0 a N-1 , y para cada índice actual i, hacer lo siguiente:
    • Inicialice una variable, digamos bandera a 0 .
    • Iterar de 0 a 30 , y para cada índice actual j , hacer lo siguiente:
      • Si la diferencia entre 2 j y arr[i] es igual a arr[i], y la frecuencia de arr[i] es mayor que 1 , incremente la bandera y rompa.
      • De lo contrario, si la frecuencia de la diferencia entre 2 j y arr[i] es mayor que 0 , incremente la bandera y rompa.
    • Si el indicador sigue siendo 0 , incremente ans, ya que el elemento actual debe eliminarse.
  • Finalmente, después de completar los pasos anteriores, imprima el recuento del elemento eliminado como el valor obtenido en ans , si es menor que N. De lo contrario, imprima -1.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum
// number of elements to be removed
// satisfying the conditions
int minimumDeletions(int arr[], int N)
{
    // Stores the final answer
    int ans = 0;
 
    // Map to store frequency
    // of each element
    map<int, int> mp;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
        mp[arr[i]]++;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        // Stores whether current
        // element needs to be
        // removed or not
        int flag = 0;
 
        // Iterate over the range
        // [0, 30]
        for (int j = 0; j < 31; j++) {
 
            // Stores 2^j
            int pw = (1 << j);
 
            // If 2^j -arr[i] equals
            // to the arr[i]
            if (pw - arr[i] == arr[i]) {
 
                // If count of arr[i]
                // is greater than 1
                if (mp[arr[i]] > 1) {
                    flag = 1;
                    break;
                }
            }
            // Else if count of 2^j-arr[i]
            // is greater than 0
            else if (mp[pw - arr[i]] > 0) {
                flag = 1;
                break;
            }
        }
        // If flag is 0
        if (flag == 0)
            ans++;
    }
    // Return ans
    return ans == N ? -1 : ans;
}
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << minimumDeletions(arr, N) << endl;
 
    int arr1[] = { 1, 5, 10, 25, 50 };
    N = sizeof(arr) / sizeof(arr[0]);
    cout << minimumDeletions(arr1, N) << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
    // Function to calculate the minimum
    // number of elements to be removed
    // satisfying the conditions
    static int minimumDeletions(int []arr, int N)
    {
       
        // Stores the final answer
        int ans = 0;
     
        // Map to store frequency
        // of each element
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
     
        // Traverse the array arr[]
        for (int i = 0; i < N; i++){
            if(mp.containsKey(arr[i]))
              mp.put(arr[i],mp.get(arr[i]) + 1);
            else
              mp.put(arr[i],1);
        }
     
        // Traverse the array arr[]
        for (int i = 0; i < N; i++)
        {
           
            // Stores whether current
            // element needs to be
            // removed or not
            int flag = 0;
     
            // Iterate over the range
            // [0, 30]
            for (int j = 0; j < 31; j++) {
     
                // Stores 2^j
                int pw = (1 << j);
     
                // If 2^j -arr[i] equals
                // to the arr[i]
                if (pw - arr[i] == arr[i]) {
     
                    // If count of arr[i]
                    // is greater than 1
                    if (mp.containsKey(arr[i]) && mp.get(arr[i]) > 1) {
                        flag = 1;
                        break;
                    }
                }
               
                // Else if count of 2^j-arr[i]
                // is greater than 0
                else if (mp.containsKey(pw - arr[i]) && mp.get(pw - arr[i]) > 0) {
                    flag = 1;
                    break;
                }
            }
           
            // If flag is 0
            if (flag == 0)
                ans++;
        }
       
        // Return ans
        if(ans == N)
         return -1;
        else
         return ans;
     
    }
       
    // Driver Code
    public static void main(String[] args)
    {
     
        int arr[] = { 1, 2, 3, 4, 5, 6 };
        int N = arr.length;
     
        System.out.println(minimumDeletions(arr, N));
     
        int arr1[] = { 1, 5, 10, 25, 50 };
        N = arr1.length;
        System.out.print(minimumDeletions(arr1, N));
     
    }
}
 
// This code is contributed by ShubhamSingh10

Python3

# Py program for the above approach
 
# Function to calculate the minimum
# number of elements to be removed
# satisfying the conditions
def minimumDeletions(arr, N):
    # Stores the final answer
    ans = 0
 
    # Map to store frequency
    # of each element
    mp = {}
 
    # Traverse the array arr[]
    for i in arr:
        mp[i] =  mp.get(i,0)+1
 
    # Traverse the array arr[]
    for i in range(N):
        # Stores whether current
        # element needs to be
        # removed or not
        flag = 0
 
        # Iterate over the range
        # [0, 30]
        for j in range(31):
            # Stores 2^j
            pw = (1 << j)
 
            # If 2^j -arr[i] equals
            # to the arr[i]
            if i >= len(arr):
                break
 
            if (pw - arr[i] == arr[i]):
 
                # If count of arr[i]
                # is greater than 1
                if (mp[arr[i]] > 1):
                    flag = 1
                    break
            # Else if count of 2^j-arr[i]
            # is greater than 0
            elif (((pw - arr[i]) in mp) and mp[pw - arr[i]] > 0):
                flag = 1
                break
 
        # If flag is 0
        if (flag == 0):
            ans += 1
    # Return ans
    return -1 if ans == N else ans
   
# Driver Code
if __name__ == '__main__':
 
    arr= [1, 2, 3, 4, 5, 6]
    N = len(arr)
 
    print (minimumDeletions(arr, N))
 
    arr1= [1, 5, 10, 25, 50]
    N = len(arr)
    print (minimumDeletions(arr1, N))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate the minimum
// number of elements to be removed
// satisfying the conditions
static int minimumDeletions(int []arr, int N)
{
   
    // Stores the final answer
    int ans = 0;
 
    // Map to store frequency
    // of each element
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++){
        if(mp.ContainsKey(arr[i]))
          mp[arr[i]] += 1;
        else
          mp.Add(arr[i],1);
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
       
        // Stores whether current
        // element needs to be
        // removed or not
        int flag = 0;
 
        // Iterate over the range
        // [0, 30]
        for (int j = 0; j < 31; j++) {
 
            // Stores 2^j
            int pw = (1 << j);
 
            // If 2^j -arr[i] equals
            // to the arr[i]
            if (pw - arr[i] == arr[i]) {
 
                // If count of arr[i]
                // is greater than 1
                if (mp.ContainsKey(arr[i]) && mp[arr[i]] > 1) {
                    flag = 1;
                    break;
                }
            }
           
            // Else if count of 2^j-arr[i]
            // is greater than 0
            else if (mp.ContainsKey(pw - arr[i]) && mp[pw - arr[i]] > 0) {
                flag = 1;
                break;
            }
        }
       
        // If flag is 0
        if (flag == 0)
            ans++;
    }
   
    // Return ans
    if(ans == N)
     return -1;
    else
     return ans;
 
}
   
// Driver Code
public static void Main()
{
 
    int []arr = { 1, 2, 3, 4, 5, 6 };
    int N = arr.Length;
 
    Console.WriteLine(minimumDeletions(arr, N));
 
    int []arr1 = { 1, 5, 10, 25, 50 };
    N = arr1.Length;
    Console.Write(minimumDeletions(arr1, N));
 
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to calculate the minimum
// number of elements to be removed
// satisfying the conditions
function minimumDeletions(arr, N) {
    // Stores the final answer
    let ans = 0;
 
    // Map to store frequency
    // of each element
    let mp = new Map();
 
    // Traverse the array arr[]
    for (let i = 0; i < N; i++) {
        if (mp.has(arr[i])) {
            mp.set(arr[i], mp.get(arr[i]) + 1)
        } else {
            mp.set(arr[i], 1)
        }
    }
 
    // Traverse the array arr[]
    for (let i = 0; i < N; i++) {
        // Stores whether current
        // element needs to be
        // removed or not
        let flag = 0;
 
        // Iterate over the range
        // [0, 30]
        for (let j = 0; j < 31; j++) {
 
            // Stores 2^j
            let pw = (1 << j);
 
            // If 2^j -arr[i] equals
            // to the arr[i]
            if (pw - arr[i] == arr[i]) {
 
                // If count of arr[i]
                // is greater than 1
                if (mp.get(arr[i]) > 1) {
                    flag = 1;
                    break;
                }
            }
            // Else if count of 2^j-arr[i]
            // is greater than 0
            else if (mp.get(pw - arr[i]) > 0) {
                flag = 1;
                break;
            }
        }
        // If flag is 0
        if (flag == 0)
            ans++;
    }
    // Return ans
    return ans == N ? -1 : ans;
}
// Driver Code
 
let arr = [1, 2, 3, 4, 5, 6];
let N = arr.length;
 
document.write(minimumDeletions(arr, N) + "<br>");
 
let arr1 = [1, 5, 10, 25, 50];
N = arr.length;
document.write(minimumDeletions(arr1, N) + "<br>");
 
</script>
Producción: 

1
-1

 

Complejidad temporal: O(30*N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *