मान लीजिए हमारे पास धनात्मक पूर्णांकों के दो सरणी 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
