Đếm cặp phần tử mảng khác nhau K bit trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng cặp phần tử mảng khác nhau K bit trong biểu diễn nhị phân.

Cho một mảng và số nguyên K. Nhiệm vụ là tìm số cặp (i, j) sao cho số bit khác nhau giữa arr[i] và arr[j] bằng K.

Ví dụ

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

int count_bit(int n) {
    int count = 0;
    while(n) {
        if(n & 1) ++count;
        n >>= 1;
    }
    return count;
}

long long count_pair(int arr[], int n, int k) {
    long long ans = 0;
    for(int i = 0; i < n-1; ++i)
        for(int j = i + 1; j < n; ++j)
            if(k == count_bit(arr[i] ^ arr[j]))
                ++ans;
    return ans;
}

int main() {
    int k = 2;
    int arr[] = {2, 4, 1, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Total pairs for k = " << k << " are " << count_pair(arr, n, k) << "\n";
    return 0;
}

Đếm cặp phần tử mảng khác nhau K bit trong C++

Ví dụ

Kết quả