सरणी के सभी युग्मों का अधिकतम मॉड्यूल जहाँ arr[i]>=arr[j] C++ . में होता है

इस समस्या में, हमें एक सरणी दी गई है, जो n तत्वों की है। हमारा काम एक प्रोग्राम बनाना है, जहां arr[i]>=arr[j]. के सभी युग्मों के अधिकतम मॉड्यूलो का पता लगाया जा सके।

यहाँ, हमें arr[i] % arr[j] का अधिकतम मान ज्ञात करना है जहाँ arr[i]>=arr[j]।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - गिरफ्तारी [] ={3, 5, 9}

आउटपुट -4

स्पष्टीकरण -

All possible Pairs arr[i] and arr[j],
5, 3 => 5%3 = 2
9, 3 => 9%3 = 0
9, 5 => 9%5 = 4

इस समस्या को हल करने के लिए, एक सरल और सीधा दृष्टिकोण दो नेस्टेड लूप चलाए जाएंगे और प्रत्येक संभावित जोड़ी के लिए मॉड्यूल ढूंढेंगे। फिर, उनमें से अधिकतम खोजें। लेकिन, यह समाधान कुशल नहीं होगा क्योंकि इसकी जटिलता क्रम O(n^2) की होगी।

क्रमबद्ध सरणी पर एक प्रभावी दृष्टिकोण लागू किया जाएगा। एल्गोरिथम हम निम्नलिखित तरीके से लागू करेंगे -

सरणी में प्रत्येक तत्व arr[j] के लिए, हमें वे मान मिलेंगे जो arr[j] x के गुणज हैं, जब तक कि हम सरणी के सबसे बड़े तत्व से अधिक मान नहीं पाते। फिर, हम एक सरणी के सभी मान पाएंगे जैसे कि arr[i]

आइए इस समाधान का उपयोग करके एक उदाहरण हल करते हैं जो एल्गोरिथम की कार्यप्रणाली दिखाएगा -

arr = {3, 5, 9}
arr[j] = 3 for j = 0,
x = {6, 9}
For x = 6, arr[i] = 5,
arr[i]%arr[j] = 6%5 = 2, maxModulo = 2
For x = 9, arr[i] = 9,
arr[i]%arr[j] = 9%3 = 0, maxModulo = 2
arr[j] = 5 for j = 1,
x = {10}
For x = 10, arr[i] = 9,
arr[i]%arr[j] = 9%5 = 4, maxModulo =4

उदाहरण

ऐरे के सभी युग्मों के अधिकतम मॉड्यूल को खोजने के लिए प्रोग्राम जहां arr[i]>=arr[j] −

#include <bits/stdc++.h>
using namespace std;
int maxModulo(int arr[], int n) {
   int maxModulo = 0;
   sort(arr, arr + n);
   for (int j = n - 2; j >= 0; --j) {
      if (maxModulo >= arr[j])
         break;
      if (arr[j] == arr[j + 1])
         continue;
      for (int k = 2 * arr[j]; k <= arr[n - 1] + arr[j]; k += arr[j]) {
         int i = lower_bound(arr, arr + n, k) - arr;
         maxModulo = max(maxModulo, arr[i - 1] % arr[j]);
      }
   }
   return maxModulo;
}
int main() {
   int arr[] = {3, 5, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum modulo of all pairs is "<<maxModulo(arr, n);
}

आउटपुट

The maximum modulo of all pairs is 4