Số bộ ba có AND bitwise bằng 0 trong C++

Cho mảng A. Tìm số bộ ba chỉ số (i, j, k) sao cho A[i] & A[j] & A[k] == 0 (AND bitwise).

Ví dụ: [3,1,2] → 12 bộ ba.

Giải thuật

1. Tính tần suất của tất cả các giá trị A[i] & A[j] (với mọi cặp i, j) lưu vào map m.
2. Duyệt từng phần tử x = A[i], với mỗi cặp (key, value) trong m: nếu (key & x) == 0 thì cộng value vào kết quả.
3. Độ phức tạp: O(n² + n * số_key_trong_map).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int countTriplets(vector<int>& A){
        unordered_map<int, int> m;
        int ret = 0;
        int n = A.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                m[A[i] & A[j]]++;
        for (int i = 0; i < n; i++) {
            int x = A[i];
            for (auto& a : m)
                if ((a.first & x) == 0) ret += a.second;
        }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<int> v = {3,1,2};
    cout << (ob.countTriplets(v));
}

Đầu vào

{3,1,2}

Đầu ra

12