C++ में ऐरे के सभी जोड़े का अधिकतम मॉड्यूलो जहां arr[i] >= arr[j]

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

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

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट - arr[] = {3, 5, 9}

आउटपुट - 4

व्याख्या -

सभी संभावित जोड़े arr[i] और 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] < x। arr[i] % arr[j] ढूंढें, और प्रत्येक ऑपरेशन के बाद मॉड्यूलो मान के अधिकतम को maxModulo वेरिएबल में स्टोर करें।

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

arr = {3, 5, 9} 
arr[j] = 3, j = 0 के लिए, x = {6, 9} 
x = 6 के लिए, arr[i] = 5, arr[i]%arr[j] = 6%5 = 2, maxModulo = 2 
x = 9 के लिए, arr[i] = 9, arr[i]%arr[j] = 9%3 = 0, maxModulo = 2 
arr[j] = 5, j = 1 के लिए, x = {10} 
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