C++中求和为2的幂的数对个数

给定一个数组，我们必须找到和为2的幂的数对的个数。让我们来看一个例子。

输入

arr = [1, 2, 3]

输出

1

只有一对数的和是2的幂。这对数是(1, 3)。

算法

  • 用随机数初始化数组。
  • 将计数初始化为0。
  • 编写两个循环以获取数组的所有对。
    • 计算每一对的和。
    • 使用按位与运算符检查和是否为2的幂。
    • 如果计数是2的幂，则递增计数。
  • 返回计数。

实现

以下是上述算法在C++中的实现

#include <bits/stdc++.h>
using namespace std;
int get2PowersCount(int arr[], int n) {
   int count = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         int sum = arr[i] + arr[j];
         if ((sum & (sum - 1)) == 0) {
            count++;
         }
      }
   }
   return count;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   int n = 10;
   cout << get2PowersCount(arr, n) << endl;
   return 0;
}

输出

如果运行上面的代码，则会得到以下结果。

6

更新于：2021年10月26日

821 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告