满足 Ai & Aj = 0 的有序对的数量

---

假设给定一个数组，你需要找到形成的有序对的总数，使得Ai & Aj = 0。

给定一个数组 A[A1, A2, A3,…An]。你需要找到 Ai 和 Aj 的有序对，使得它们的按位与运算结果等于 0。换句话说，你需要计算按位与运算结果为零的元素对 (i, j) 的数量。

例如，我们有一个数组 [3, 4, 2]。每个元素的二进制表示如下：

• A1 = 3 = 011

• A2 = 4 = 100

• A3 = 2 = 010

按位与运算的结果对为：

A1 & A2 = 0, A2 & A3 = 0, A2 & A1 = 0, A3 & A2 = 0

对于其余的对，结果不为零。因此，我们需要找到结果为 0 的对。

输入输出场景

给定 N。输出 N 位非递减整数的数量。

Input: arr[] = {1, 5, 4, 3}
Output: 4
Input: arr[] = {11, 5, 20, 6, 3}
Output: 10

使用迭代

我们可以简单地遍历数组所有可能的元素对，并对它们进行按位与运算。如果结果为 0，则计数变量增加 2。这是因为如果 (i, j) 的结果为零，那么 (j, i) 的结果也一样。这里，(i, j) 和 (j, i) 被认为是不同的。

示例

#include <iostream>
using namespace std;
int possiblePairs(int arr[], int N){
   int count = 0;
   for(int j = 0; j < N; j++){
      for(int k = j + 1; k < N; k++){
         if((arr[j] & arr[k]) == 0){
            count += 2;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {1, 5, 4, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout << "Number of ordered pairs such that (arr[j] & arr[k] = 0) is " <<
   possiblePairs(arr, N) << endl;
   return 0;
}

输出

Number of ordered pairs such that (arr[j] & arr[k] = 0) is 4

使用“unordered_map”数据结构

我们将使用unordered_map数据结构来计算此类对的总数。我们将使用哈希的概念来轻松定位我们的数据记录。在嵌套循环中，按位与运算的结果存储在无序映射中。从该映射中检索数据并存储在计数变量中。

示例

#include <iostream>
#include <unordered_map>
using namespace std;
int possiblePairs(int arr[], int N) {
   unordered_map < int, int > result;
   for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
         if ((arr[j] & arr[k]) == 0) {
            result[arr[j]]++;
         }
      }
   }
   int count = 0;
   for (auto it: result) {
      count += it.second;
   }
   return count;
}
int main() {
   int arr[] = { 1, 5, 4, 3 };
   int N = sizeof(arr) / sizeof(arr[0]);
   cout << "Number of ordered pairs such that (arr[j] & arr[k] = 0) is " <<
   possiblePairs(arr, N) << endl;
   return 0;
}

输出

Number of ordered pairs such that (arr[j] & arr[k] = 0) is 4

使用位掩码和二维数组

我们使用unordered_map存储数组元素的频率。它们以整数形式存储键和值。我们使用二维数组da存储中间结果。接下来，我们使用位掩码以数组元素子集的形式表示元素的二进制表示。

然后，我们遍历所有掩码值以检查元素对之间的按位与运算。使用按位计算和二维数组，我们找到此类对的总数。

示例

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int X = 15;
long long possiblePairs(int arr[], int N) {
   // Declaration
   unordered_map<int, int> num;
   long long da[1 << X][X + 1];
   // Initialize all values to 0
   memset(da, 0, sizeof(da));
   for (int i = 0; i < N; ++i)
   num[arr[i]]++;
   for (long long mask = 0; mask < (1 << X); ++mask) {
      if (mask & 1)
      da[mask][0] = num[mask] + num[mask ^ 1];
      else
      da[mask][0] = num[mask];
      for (int i = 1; i <= X; ++i) {
         if (mask & (1 << i))
         da[mask][i] = da[mask][i - 1] +
         da[mask ^ (1 << i)][i - 1];
         else
         da[mask][i] = da[mask][i - 1];
      }
   }
   long long result = 0;
   for (int i = 0; i < N; i++)
   result += da[((1 << X) - 1) ^ arr[i]][X];
   return result;
}
int main() {
   int arr[] = {1, 5, 4, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout << "Number of ordered pairs such that (arr[j] & arr[k] = 0) is " <<
   possiblePairs(arr, N) << endl;
   return 0;
}

输出

Number of ordered pairs such that (arr[j] & arr[k] = 0) is 4

结论

我们讨论了查找满足Ai & Aj = 0的有序对数量的不同方法。第一种方法是使用嵌套 for 循环的简单方法。第二种方法使用“unordered_map”数据结构，是一种空间优化方法。在第三种方法中，我们使用位掩码函数和二维数组，使代码更有效率。