和为 2 的幂的偶对数量 | 系列 2
原文：https://www.geeksforgeeks.org/number-of-pairs-whose-sum-is-a-power-of-2-set-2/
给定由N个正整数组成的数组arr[]，任务是计算对数arr[i], arr[j]，使得arr[i] + arr[j]是 2 的幂。
示例：
输入：
arr[] = {1, -1, 2, 3}输出：5
说明：
(1, 1), (2, 2), (1, 3), (-1, 3), (-1, 2)是有效对，其和为 2 的幂。输入：
arr[] = {1, 1, 1}输出：6
朴素的方法：解决该问题的最简单方法是从给定数组生成所有可能的对，并且对于每对，检查该对的和是否是 2 的幂。
*时间复杂度：O(N ^ 2)。
辅助空间：O(1)*
有效方法：可以使用HashMap优化上述方法。 请按照以下步骤解决问题：
-
初始化变量
count以存储总和等于 2 的任何幂的偶对计数。 -
遍历范围
[0, 31]并生成 2 的所有幂，即2 ^ 0至2 ^ 31。 -
遍历给定的数组，每产生 2 的幂，并检查
map[key - arr[j]]是否存在，其中键等于2 ^ i。 -
如果发现是真的，则将
count增加map[key – arr[j]]，偶对(arr[j], key – arr[j])的和等于 2 的幂。 -
最后，打印
count / 2作为所需答案。
下面是上述方法的实现：
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 for 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));
}
}
输出：
5
时间复杂度：O(NlogN)。
辅助空间：O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
