โมดูโลสูงสุดของทุกคู่ของอาร์เรย์โดยที่ arr[i]>=arr[j] ใน C++

ในปัญหานี้ เราจะได้รับอาร์เรย์ที่มีองค์ประกอบ 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] ในอาร์เรย์ เราจะพบค่าที่เป็นทวีคูณของ arr[j] พูด x จนกว่าเราจะพบค่าที่มากกว่าองค์ประกอบที่ใหญ่ที่สุดของอาร์เรย์ จากนั้นเราจะหาค่าทั้งหมดของอาร์เรย์ที่ 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