এই সমস্যায়, আমাদের 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
