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 3 ). 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 )
(1, 1023) con suma 1024 (= 2 10 )
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 0 , 2 1 , …., 2 30 } y verifique si p – a[i] está presente en el arreglo o no.
- Cualquiera de las dos condiciones siguientes debe cumplirse:
- 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.
- Si s está presente solo una vez en el arreglo, entonces s tiene que ser diferente de a[i] para un posible par.
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
1
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)