滿足 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”資料結構，是一種空間最佳化方法。在第三種方法中，我們使用位掩碼函式和二維陣列，使程式碼更有效率。