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

คำอธิบายปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ที่มี n องค์ประกอบ งานของเราคือสร้าง โปรแกรมเพื่อหาค่าส่วนเหลือ (modulo) สูงสุดของทุกคู่ในอาร์เรย์ที่ 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)

วิธีที่มีประสิทธิภาพจะนำไปใช้กับอาร์เรย์ที่เรียงลำดับแล้ว อัลกอริทึมจะทำงานดังนี้:

สำหรับแต่ละองค์ประกอบ arr[j] ในอาร์เรย์ เราจะหาค่าที่เป็นพหุคูณของ arr[j] ให้เป็น x จนกว่าจะพบค่าที่มากกว่าองค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์ จากนั้น เราจะหาค่าทั้งหมดในอาร์เรย์ที่ arr[i] < x หา arr[i] % arr[j] และเก็บค่าส่วนเหลือสูงสุดไว้ในตัวแปร maxModulo หลังจากการดำเนินการแต่ละครั้ง

มาลองแก้ตัวอย่างด้วยวิธีนี้ ซึ่งจะแสดงการทำงานของอัลกอริทึม –

arr = {3, 5, 9} arr[j] = 3 สำหรับ j = 0, x = {6, 9} สำหรับ x = 6, arr[i] = 5, arr[i]%arr[j] = 6%5 = 2, maxModulo = 2 สำหรับ x = 9, arr[i] = 9, arr[i]%arr[j] = 9%3 = 0, maxModulo = 2 arr[j] = 5 สำหรับ j = 1, x = {10} สำหรับ 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