इस समस्या में, हमें n तत्वों की एक सरणी दी गई है। हमारा काम एक प्रोग्राम बनाना है जो किसी दिए गए सरणी के लिए arr[i]%arr[j] का अधिकतम मान पायेगा।
इसलिए, मूल रूप से हमें सरणी के दो तत्वों को विभाजित करते हुए अधिकतम शेषफल का मान ज्ञात करना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी{3, 6, 9, 2, 1}
आउटपुट -6
स्पष्टीकरण -
3%3 = 0; 3%6 = 3; 3%9 = 3; 3%2 = 1; 3%1 = 0 6%3 = 0; 6%6 = 0; 6%9 = 6; 6%2 = 0; 6%1 =0 9%3 = 0; 9%6 = 3; 9%9 = 0 9%2 = 1; 9%1 = 0 2%3 = 2; 2%6 = 2; 2%9 = 2; 2%2 = 0; 2%1 = 0 1%3 = 1; 1%6 = 1; 1%9 = 1; 1%2 =1; 1%1 = 0 Out the above remainders the maximum is 6.
इसलिए, समाधान खोजने का एक सीधा तरीका यह होगा कि प्रत्येक जोड़े के लिए शेषफल की गणना की जाए और फिर उनमें से अधिकतम का पता लगाया जाए। लेकिन यह तरीका कारगर नहीं होगा क्योंकि इसकी समय जटिलता क्रम n 2 की होगी ।
तो, एक प्रभावी समाधान इस तर्क का उपयोग करेगा कि x%y का मान अधिकतम होगा जब y>x तब शेष x होगा। और सरणी के सभी तत्वों में से यदि हम दो अधिकतम तत्व लेते हैं, तो परिणाम अधिकतम होगा। इसके लिए, हम सरणी को सॉर्ट करेंगे और फिर परिणाम प्रदान करने के लिए अंतिम और दूसरे अंतिम तत्व को पुनरावृत्त करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने के लिए कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int maxRemainder(int arr[], int n){
bool hasSameValues = true;
for(int i = 1; i<n; i++) {
if (arr[i] != arr[i - 1]) {
hasSameValues = false;
break;
}
}
if (hasSameValues)
return 0;
sort(arr, arr+n);
return arr[n-2];
}
int main(){
int arr[] = { 3, 6, 9, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum remainder on dividing two elements of the array is "<<maxRemainder(arr, n);
return 0;
} आउटपुट
The maximum remainder on dividing two elements of the array is 6