इस समस्या में, हमें n एलिमेंट्स का एक ऐरे दिया गया है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो दिए गए ऐरे के लिए arr[i]%arr[j] का अधिकतम मान ढूंढे।
तो, मूल रूप से हमें ऐरे के दो एलिमेंट्स को विभाजित करते समय अधिकतम शेषफल का मान ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट − array{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 उपरोक्त शेषफलों में से अधिकतम 6 है।
तो, समाधान खोजने का एक सीधा दृष्टिकोण प्रत्येक जोड़ी के लिए शेषफल की गणना करना और फिर उन सभी में से अधिकतम ढूंढना होगा। लेकिन यह दृष्टिकोण प्रभावी नहीं होगा क्योंकि इसकी समय जटिलता n2 क्रम की होगी।
तो, एक प्रभावी समाधान इस तर्क का उपयोग करना होगा कि 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