Đếm cặp AND bitwise lẻ trong C++

Cho mảng số nguyên. Đếm cặp (i,j) (i < j) sao cho arr[i] & arr[j] là số lẻ.

Nhận xét: AND lẻ khi cả hai đều lẻ (bit LSB = 1). Kết quả = C(odd, 2) = odd*(odd-1)/2.

Ví dụ: {2,5,1,8,9,2,7} → Lẻ: 4 → Kết quả: 6.

Ví dụ

#include <iostream>
using namespace std;

int count_pair(int arr[], int size) {
    int odd = 0;
    for (int i = 0; i < size; i++)
        if (arr[i] % 2 == 1) odd++;
    return odd * (odd - 1) / 2;
}

int main() {
    int arr[] = {2,5,1,8,9,2,7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << count_pair(arr, size);
    return 0;
}

Đầu ra

Count of pairs with Bitwise AND as ODD number are: 6