Đếm cặp OR bitwise nhỏ hơn Max trong C++

Cho mảng số nguyên. Đếm cặp (i,j) (i < j) sao cho arr[i] | arr[j] <= max(arr[i], arr[j]).

Nhận xét: a | b <= max(a,b) chỉ xảy ra khi các bit của số nhỏ là tập con của bit số lớn (số nhỏ "nằm trong" số lớn về mặt bit).

Ví dụ: {2,5,1,8,9} → 3 (cặp (5,1), (8,9), (5,5) nếu cho phép trùng).

Ví dụ

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

int Pair_OR(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size - 1; i++)
        for (int j = i + 1; j < size; j++)
            if ((arr[i] | arr[j]) <= max(arr[i], arr[j]))
                count++;
    return count;
}

int main() {
    int arr[] = {4,8,9,10,23};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << Pair_OR(arr, size);
    return 0;
}

Đầu ra

Count of pairs with bitwise OR less than Max are: 3