একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। যেসব যোড়ার বিটওয়াইজ OR ফলাফল সেই যোড়ার ম্যাক্সিমাম মান থেকে ছোট বা সমান, তাদের সংখ্যা গণনা করুন।
শর্ত
(arr[i] | arr[j]) <= max(arr[i], arr[j])
উদাহরণ
ইনপুট: [2, 5, 1, 8, 9]
যোড়া যাচাই:
- (5,1): 5|1=5 ≤ max(5,1)=5 ✓
- (8,9): 8|9=9 ≤ max(8,9)=9 ✓
- (2,5): 2|5=7 > max(2,5)=5 ✗
আউটপুট: 3
মূল ইনসাইট
a | b <= max(a,b) শুধু তখনই সত্য হয় যখন ছোট সংখ্যাটির সব সেট বিট বড় সংখ্যাতেও সেট থাকে। অর্থাৎ ছোট সংখ্যা বড় সংখ্যার সাবমাস্ক (submask)।
C++ বাস্তবায়ন
#include
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 << "OR <= Max pairs: " << Pair_OR(arr, size);
return 0;
}
অপ্টিমাইজেশন (O(n log max))
প্রতিটি সংখ্যার জন্য তার সাবমাস্কগুলো খুঁজে বের করে ফ্রিকোয়েন্সি ম্যাপে লুকআপ করলে বড় ইনপুটের জন্য দ্রুত হবে।
