ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার দুটি অ্যারে X এবং Y আছে। জোড়ার সংখ্যা নির্ণয় করুন যেমন x^y> y^x, যেখানে x হল X এর একটি উপাদান এবং y হল Y এর একটি উপাদান। ধরুন X =[2, 1, 6], এবং Y =[1, 5] , তাহলে আউটপুট হবে 3। যেহেতু তিনটি জোড়া আছে, সেগুলো হল (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
