ค่าสูงสุดของ arr[i] % arr[j] สำหรับอาร์เรย์ที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของ n องค์ประกอบ งานของเราคือสร้างโปรแกรมที่จะหาค่าสูงสุดของ arr[i]%arr[j] สำหรับอาร์เรย์ที่กำหนด

โดยพื้นฐานแล้ว เราต้องหาค่าของเศษสูงสุดขณะหารสององค์ประกอบของอาร์เรย์

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - array{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
จากเศษข้างต้น ค่าสูงสุดคือ 6

ดังนั้น วิธีโดยตรงในการหาคำตอบจะเป็นการคำนวณเศษสำหรับทุกคู่และจากนั้นหาค่าสูงสุดของทั้งหมด แต่วิธีนี้จะไม่มีประสิทธิภาพเพราะ time complexity จะเป็นของออเดอร์ n²

ดังนั้น วิธีแก้ปัญหาที่มีประสิทธิภาพจะเป็นการใช้ตรรกะที่ว่า ค่าของ 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