Dada una array arr[] que consta de N enteros, la tarea es contar el número máximo de pares (arr[i], arr[j]) tal que arr[i] + arr[j] sea una potencia de 2 .
Ejemplos:
Entrada: arr[] = {1, -1, 2, 3}
Salida: 5
Explicación: (1, 1), (2, 2), (1, 3), (-1, 3), (-1, 2) son los pares válidos cuya suma es potencia de 2.Entrada: arr[] = {1, 1, 1}
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles a partir de una array dada y, para cada par, verificar si la suma del par es una potencia de 2 o no .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando HashMap . Siga los pasos a continuación para resolver el problema:
- Cree un mapa para almacenar la frecuencia de cada elemento de la array arr[] .
- Inicialice una variable ans para almacenar el recuento de pares con una suma igual a cualquier potencia de 2 .
- Atraviesa el rango [0, 31] y genera todas las potencias de 2, es decir, 2 0 a 2 31 .
- Recorra la array dada para cada potencia de 2 generada y verifique si map[key – arr[j]] existe o no, donde key es igual a 2 i .
- Si se determina que es cierto, aumente la cuenta en map[key – arr[j]] , ya que existen pares ( arr[j], key – arr[j]) con una suma igual a una potencia de 2 .
- Finalmente, imprima count / 2 como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count all pairs
// whose sum is a power of two
int countPair(int arr[], int n)
{
// Stores the frequency of
// each element of the array
map<int, int> m;
// Update frequency of
// array elements
for (int i = 0; i < n; i++)
m[arr[i]]++;
// Stores count of
// required pairs
int ans = 0;
for (int i = 0; i < 31; i++) {
// Current power of 2
int key = pow(2, i);
// Traverse the array
for (int j = 0; j < n; j++) {
int k = key - arr[j];
// If pair does not exist
if (m.find(k) == m.end())
continue;
// Increment count of pairs
else
ans += m[k];
if (k == arr[j])
ans++;
}
}
// Return the count of pairs
return ans / 2;
}
// Driver Code
int main()
{
int arr[] = { 1, 8, 2, 10, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPair(arr, n) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to count all pairs
// whose sum is power of two
static int countPair(int[] arr, int n)
{
// Stores the frequency of
// each element of the array
Map<Integer, Integer> m
= new HashMap<>();
// Update the frequency of
// array elements
for (int i = 0; i < n; i++)
m.put(arr[i], m.getOrDefault(
arr[i], 0)
+ 1);
// Stores the count of pairs
int ans = 0;
// Generate powers of 2
for (int i = 0; i < 31; i++) {
// Generate current power of 2
int key = (int)Math.pow(2, i);
// Traverse the array
for (int j = 0; j < arr.length;
j++) {
int k = key - arr[j];
// Increase ans by m[k], if
// pairs with sum 2^i exists
ans += m.getOrDefault(k, 0);
// Increase ans again if k = arr[j]
if (k == arr[j])
ans++;
}
}
// Return count of pairs
return ans / 2;
}
// Driver function
public static void main(String[] args)
{
int[] arr = { 1, -1, 2, 3 };
int n = arr.length;
System.out.println(countPair(arr, n));
}
}
Python3
# Python3 program to implement
# the above approach
from math import pow
# Function to count all pairs
# whose sum is a power of two
def countPair(arr, n):
# Stores the frequency of
# each element of the array
m = {}
# Update frequency of
# array elements
for i in range(n):
m[arr[i]] = m.get(arr[i], 0) + 1
# Stores count of
# required pairs
ans = 0
for i in range(31):
# Current power of 2
key = int(pow(2, i))
# Traverse the array
for j in range(n):
k = key - arr[j]
# If pair does not exist
if k not in m:
continue
# Increment count of pairs
else:
ans += m.get(k, 0)
if (k == arr[j]):
ans += 1
# Return the count of pairs
return ans // 2
# Driver Code
if __name__ == '__main__':
arr = [ 1, 8, 2, 10, 6 ]
n = len(arr)
print(countPair(arr, n))
# This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count all pairs
// whose sum is a power of two
function countPair(arr, n)
{
// Stores the frequency of
// each element of the array
var m= new Map();
// Update frequency of
// array elements
for (var i = 0; i < n; i++)
{
if(m.has(arr[i]))
m.set(arr[i], m.get(arr[i])+1)
else
m.set(arr[i], 1)
}
// Stores count of
// required pairs
var ans = 0;
for (var i = 0; i < 31; i++) {
// Current power of 2
var key = Math.pow(2, i);
// Traverse the array
for (var j = 0; j < n; j++) {
var k = key - arr[j];
// If pair does not exist
if (!m.has(k))
continue;
// Increment count of pairs
else
ans += m.get(k);
if (k == arr[j])
ans++;
}
}
// Return the count of pairs
return ans / 2;
}
// Driver Code
var arr = [1, 8, 2, 10, 6]
var n = arr.length
document.write( countPair(arr, n));
</script>
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count all pairs
// whose sum is a power of two
public static int countPair(int[] arr, int n)
{ // Stores the frequency of
// each element of the array
Dictionary<int, int> map
= new Dictionary<int, int>();
// Update frequency of
// array elements
for (int i = 0; i < n; i++) {
if (!map.ContainsKey(arr[i])) {
map[arr[i]] = 0;
}
map[arr[i]] = map[arr[i]] + 1;
}
// Stores count of
// required pairs
int ans = 0;
for (int i = 0; i < 31; i++) {
// Current power of 2
int key = 1 << i;
// Traverse the array
for (int j = 0; j < n; j++) {
int k = key - arr[j];
// If pair does not exist
if (!map.ContainsKey(k)) {
continue;
}
else {
// Increment count of pairs
ans += map[k];
}
if (k == arr[j]) {
ans++;
}
}
}
// Return the count of pairs
return ans / 2;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 8, 2, 10, 6 };
int n = arr.Length;
Console.WriteLine(countPair(arr, n));
}
}
// This code is contributed by Naveen Shah
Producción
5
Producción:
5
Complejidad Temporal: O(NlogN)
Espacio Auxiliar: O(N). Estamos usando un mapa para almacenar elementos.