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:
- Para 1, existe 3 tal que (1+3=4) es una potencia de 2.
- Para 2, existe 6 tal que (2+6=8) es una potencia de 2.
- Para 3, existe 1 tal que (3+1=4) es una potencia de 2.
- Para 5, existe 3 tal que (5+3=8) es una potencia de 2.
- 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