Giá trị lớn nhất của arr[i] % arr[j] cho một mảng cho trước trong C++

Trong bài toán này, chúng ta được cho một mảng n phần tử. Nhiệm vụ là tạo một chương trình tìm giá trị lớn nhất của arr[i]%arr[j] cho mảng cho trước.

Về cơ bản, chúng ta cần tìm giá trị dư lớn nhất khi chia hai phần tử của mảng.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào – mảng{3, 6, 9, 2, 1}

Đầu ra – 6

Giải thích –

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
Trong các dư số trên, giá trị lớn nhất là 6.

Vì vậy, một cách tiếp cận trực tiếp để tìm giải pháp sẽ là tính dư cho từng cặp và sau đó tìm giá trị lớn nhất của tất cả chúng. Nhưng cách tiếp cận này sẽ không hiệu quả vì độ phức tạp thời gian sẽ bậc hai.

Vì vậy, một giải pháp hiệu quả sẽ sử dụng logic rằng giá trị của x%y sẽ lớn nhất khi y > x, khi đó dư sẽ là x. Và trong tất cả các phần tử của mảng, nếu chúng ta lấy hai phần tử lớn nhất, kết quả sẽ lớn nhất. Để làm điều này, chúng ta sẽ sắp xếp mảng và sau đó lặp qua phần tử cuối cùng và phần tử áp chót để cung cấp kết quả.

Ví dụ

Chương trình minh họa triển khai giải pháp của chúng ta:

#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<<"Dư lớn nhất khi chia hai phần tử của mảng là "<<maxRemainder(arr, n);
    return 0;
}

Kết quả

Dư lớn nhất khi chia hai phần tử của mảng là 6