Đếm cặp trong mảng có số bit 1 bằng nhau trong C++

Giới thiệu

Cho mảng số nguyên, đếm số cặp (i, j) với i < j sao cho số bit 1 (set bits) trong biểu diễn nhị phân của hai số bằng nhau.

Ví dụ

arr = [6,5,1,3,7] → Bit counts: 6(2), 5(2), 1(1), 3(2), 7(3) → Cặp bằng nhau: (6,5), (6,3), (5,3) → Kết quả: 3

Ý tưởng giải thuật

1. Tính số bit 1 cho mỗi phần tử (__builtin_popcount).
2. Dùng unordered_map đếm tần suất mỗi giá trị bit count.
3. Với mỗi tần suất f, số cặp = f × (f-1) / 2.
4. Tổng hợp tất cả.

Độ phức tạp O(n) thay vì O(n²).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

int countEqualSetBitPairs(vector<int> arr) {
    unordered_map<int, int> freq;
    for (int x : arr)
        freq[__builtin_popcount(x)]++;
    
    long long count = 0;
    for (auto [bits, f] : freq)
        count += 1LL * f * (f - 1) / 2;
    return count;
}

int main() {
    vector<int> arr = {6, 5, 1, 3, 7};
    cout << "So cap co so bit 1 bang nhau: " << countEqualSetBitPairs(arr); // 3
    return 0;
}

Đầu vào

[6,5,1,3,7]

Đầu ra

3