এই সমস্যায়, আমাদের 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) কoti।
একটি কার্যকর পদ্ধতি হলো সোর্ট করা অ্যারেতে কাজ করা। অ্যালগরিদমটি নিচেরভাবে প্রয়োগ করা হবে −
প্রতিটি উপাদান arr[j] এর জন্য, আমরা arr[j]-এর গুণফল যেসব মান (বলুন x) পাওয়া যায় সেগুলো বের করব যতক্ষণ না অ্যারের সর্বোচ্চ উপাদানের চেয়ে বড় মান পাওয়া যায়। তারপর আমরা অ্যারেতে arr[i] < x যেসব মান আছে সেগুলো খুঁজে বের করব। arr[i] % arr[j] বের করে, প্রতিটি অপারেশনের পর maxModulo ভেরিয়েবলে মডুলো মানের সর্বোচ্চ মান সংরক্ষণ করব।
এই সমাধানটি উদাহরণ দিয়ে বুঝতে নিচের গণনাটি দেখুন −
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
