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

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

Cách tiếp cận tối ưu: XOR lẻ ⇔ một chẵn một lẻ. Đếm even và odd, kết quả = even * odd.

Ví dụ: {6,1,3,4,8,9} → Chẵn: 3, Lẻ: 3 → Kết quả: 9.

Ví dụ

#include <iostream>
using namespace std;

int XOR_Odd(int arr[], int size) {
    int even = 0;
    for (int i = 0; i < size; i++)
        if (arr[i] % 2 == 0) even++;
    return even * (size - even);
}

int main() {
    int arr[] = {6,1,3,4,8,9};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << XOR_Odd(arr, size);
    return 0;
}

Đầu ra

Count of pairs with Bitwise XOR as ODD number are: 9