Dada una array arr[] de enteros positivos, la tarea es contar el máximo número posible de pares (arr[i], arr[j]) tal que arr[i] + arr[j] sea una potencia de 2 .
Nota: Un elemento puede usarse como máximo una vez para formar un par.
Ejemplos:
Entrada: arr[] = {3, 11, 14, 5, 13}
Salida: 2
Todos los pares válidos son (13, 3) y (11, 5), ambos suman 16, que es una potencia de 2.
Podríamos tener (3, 5) pero al hacerlo solo se pudo formar un máximo de 1 par.
Por lo tanto, (3, 5) no es óptima.
Entrada: arr[] = {1, 2, 3}
Salida: 1
1 y 3 se pueden emparejar para formar 4, que es una potencia de 2.
Una solución simple es considerar cada par y verificar si la suma de este par es una potencia de 2 o no. La complejidad temporal de esta solución es O(n * n)
Un enfoque eficiente: es encontrar el elemento más grande de la array, digamos X , luego encontrar el elemento más grande del resto de los elementos de la array Y , de modo que Y ≤ X y X + Y sea una potencia de 2 Esta es una selección óptima de pares porque incluso si Y hace un par válido con algún otro elemento, digamos Z , entonces se dejará que Z se empareje con un elemento que no sea Y ( si es posible) para maximizar el número de pares válidos.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of valid pairs
int countPairs(int a[], int n)
{
// Storing occurrences of each element
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[a[i]]++;
// Sort the array in decreasing order
sort(a, a + n, greater<int>());
// Start taking largest element each time
int count = 0;
for (int i = 0; i < n; i++) {
// If element has already been paired
if (mp[a[i]] < 1)
continue;
// Find the number which is greater than
// a[i] and power of two
int cur = 1;
while (cur <= a[i])
cur <<= 1;
// If there is a number which adds up with a[i]
// to form a power of two
if (mp[cur - a[i]]) {
// Edge case when a[i] and crr - a[i] is same
// and we have only one occurrence of a[i] then
// it cannot be paired
if (cur - a[i] == a[i] and mp[a[i]] == 1)
continue;
count++;
// Remove already paired elements
mp[cur - a[i]]--;
mp[a[i]]--;
}
}
// Return the count
return count;
}
// Driver code
int main()
{
int a[] = { 3, 11, 14, 5, 13 };
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.TreeMap;
class Count
{
// Function to return the count of valid pairs
static int countPairs(int[] a, int n)
{
// To keep the element in sorted order
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++)
{
map.put(a[i], 1);
}
// Start taking largest element each time
int count = 0;
for (int i = 0; i < n; i++)
{
// If element has already been paired
if (map.get(a[i]) < 1)
continue;
// Find the number which is greater than
// a[i] and power of two
int cur = 1;
while (cur <= a[i])
cur <<= 1;
// If there is a number which adds up with a[i]
// to form a power of two
if (map.containsKey(cur - a[i]))
{
// Edge case when a[i] and crr - a[i] is same
// and we have only one occurrence of a[i] then
// it cannot be paired
if (cur - a[i] == a[i] && map.get(a[i]) == 1)
continue;
count++;
// Remove already paired elements
map.put(cur - a[i], map.get(cur - a[i]) - 1);
map.put(a[i], map.get(a[i]) - 1);
}
}
// Return the count
return count;
}
// Driver code
public static void main(String[] args)
{
int[] a = { 3, 11, 14, 5, 13 };
int n = a.length;
System.out.println(countPairs(a, n));
}
}
// This code is contributed by Vivekkumar Singh
Python3
# Python3 implementation of above approach # Function to return the count # of valid pairs def countPairs(a, n) : # Storing occurrences of each element mp = dict.fromkeys(a, 0) for i in range(n) : mp[a[i]] += 1 # Sort the array in decreasing order a.sort(reverse = True) # Start taking largest element # each time count = 0 for i in range(n) : # If element has already been paired if (mp[a[i]] < 1) : continue # Find the number which is greater # than a[i] and power of two cur = 1 while (cur <= a[i]) : cur = cur << 1 # If there is a number which adds # up with a[i] to form a power of two if (cur - a[i] in mp.keys()) : # Edge case when a[i] and crr - a[i] # is same and we have only one occurrence # of a[i] then it cannot be paired if (cur - a[i] == a[i] and mp[a[i]] == 1) : continue count += 1 # Remove already paired elements mp[cur - a[i]] -= 1 mp[a[i]] -= 1 # Return the count return count # Driver code if __name__ == "__main__" : a = [ 3, 11, 14, 5, 13 ] n = len(a) print(countPairs(a, n)) # This code is contributed by Ryuga
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of valid pairs
static int countPairs(int[] a, int n)
{
// To keep the element in sorted order
Dictionary<int,
int> map = new Dictionary<int,
int>();
for (int i = 0; i < n; i++)
{
if(!map.ContainsKey(a[i]))
map.Add(a[i], 1);
}
// Start taking largest element each time
int count = 0;
for (int i = 0; i < n; i++)
{
// If element has already been paired
if (map[a[i]] < 1)
continue;
// Find the number which is greater than
// a[i] and power of two
int cur = 1;
while (cur <= a[i])
cur <<= 1;
// If there is a number which adds up
// with a[i] to form a power of two
if (map.ContainsKey(cur - a[i]))
{
// Edge case when a[i] and crr - a[i]
// is same and we have only one occurrence
// of a[i] then it cannot be paired
if (cur - a[i] == a[i] && map[a[i]] == 1)
continue;
count++;
// Remove already paired elements
map[cur - a[i]] = map[cur - a[i]] - 1;
map[a[i]] = map[a[i]] - 1;
}
}
// Return the count
return count;
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 3, 11, 14, 5, 13 };
int n = a.Length;
Console.WriteLine(countPairs(a, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to return the count of valid pairs
function countPairs(a, n)
{
// To keep the element in sorted order
let map = new Map();
for (let i = 0; i < n; i++)
{
map.set(a[i], 1);
}
// Start taking largest element each time
let count = 0;
for (let i = 0; i < n; i++)
{
// If element has already been paired
if (map.get(a[i]) < 1)
continue;
// Find the number which is greater than
// a[i] and power of two
let cur = 1;
while (cur <= a[i])
cur <<= 1;
// If there is a number which adds up with a[i]
// to form a power of two
if (map.has(cur - a[i]))
{
// Edge case when a[i] and crr - a[i] is same
// and we have only one occurrence of a[i] then
// it cannot be paired
if (cur - a[i] == a[i] && map.get(a[i]) == 1)
continue;
count++;
// Remove already paired elements
map.set(cur - a[i], map.get(cur - a[i]) - 1);
map.set(a[i], map.get(a[i]) - 1);
}
}
// Return the count
return count;
}
// Driver Code
let a = [ 3, 11, 14, 5, 13 ];
let n = a.length;
document.write(countPairs(a, n));
</script>
2
Tenga en cuenta que la operación a continuación en el código anterior se puede realizar en tiempo O (1) utilizando el último enfoque discutido en la potencia más pequeña de 2 mayor o igual que n
C
// Find the number which is greater than // a[i] and power of two int cur = 1; while (cur <= a[i]) cur <<= 1;
Javascript
// JavaScript program to find the // number which is greater than // a[i] and power of two var cur = 1; while (cur <= a[i]) cur <<= 1; //This code is contributed by phasing17
Después de optimizar la expresión anterior, la complejidad temporal de esta solución se convierte en O(n Log n)