ধরুন X এবং Y হলো দুটি ধনাত্মক পূর্ণসংখ্যার অ্যারে। এমন (x, y) জোড়াগুলোর সংখ্যা বের করতে হবে যাতে x^y > y^x, যেখানে x ∈ X এবং y ∈ Y। উদাহরণস্বরূপ, X = [2, 1, 6] এবং Y = [1, 5] হলে আউটপুট হবে ৩। কারণ তিনটি জোড়া আছে: (2, 1), (2, 5) এবং (6, 1)।
এই সমস্যাটি দক্ষতার সাথে সমাধান করা যায়। মূল লজিক হলো: যদি y > x হয়, তবে x^y > y^x হবে, কিন্তু কিছু استثনা রয়েছে। এই استثনাগুলো হ্যান্ডেল করেই সমাধান পাওয়া যায়।
- প্রথমে Y অ্যারেটি সর্ট করুন।
- X-এর প্রতিটি উপাদান x-এর জন্য, Y-তে x-র চেয়ে বড় সবচেয়ে ছোট সংখ্যার ইনডেক্স বাইনারি সার্চ (বা upper_bound ফাংশন) দিয়ে খুঁজুন।
- সেই ইনডেক্সের পরে থাকা সব সংখ্যা শর্ত পূরণ করে, তাই তাদের গণনা যোগ করুন।
#include <iostream>
#include <algorithm>
using namespace std;
int count(int x, int Y[], int n, int no_of_y[]) {
if (x == 0) return 0;
if (x == 1) return no_of_y[0];
int* index = upper_bound(Y, Y + n, x);
int ans = (Y + n) - index;
ans += (no_of_y[0] + no_of_y[1]);
if (x == 2) ans -= (no_of_y[3] + no_of_y[4]);
if (x == 3) ans += no_of_y[2];
return ans;
}
int howManyPairs(int X[], int Y[], int m, int n) {
int no_of_y[5] = {0};
for (int i = 0; i < n; i++)
if (Y[i] < 5) no_of_y[Y[i]]++;
sort(Y, Y + n);
int total_pairs = 0;
for (int i = 0; i < m; i++)
total_pairs += count(X[i], Y, n, no_of_y);
return total_pairs;
}
int main() {
int X[] = {2, 1, 6};
int Y[] = {1, 5};
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
cout << "Total pair count: " << howManyPairs(X, Y, m, n);
}
Total pair count: 3
