অ্যারের সমস্ত জোড়ার সর্বাধিক মডিউল যেখানে C++ এ arr[i]>=arr[j]

এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে, যা n উপাদানের। আমাদের কাজ হল একটি অ্যারের সমস্ত জোড়ার সর্বাধিক মডিউল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যেখানে arr[i]>=arr[j]।

এখানে, আমাদের arr[i] % arr[j] এর সর্বোচ্চ মান খুঁজে বের করতে হবে যেখানে arr[i]>=arr[j]।

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট − arr[] ={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] এর জন্য, আমরা অ্যারের সবচেয়ে বড় এলিমেন্টের থেকে বেশি মান না পাওয়া পর্যন্ত আমরা x বলে arr[j] এর গুণিতক মান খুঁজে পাব। তারপর, আমরা একটি অ্যারের সমস্ত মান খুঁজে পাব যেমন 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