Giá trị modulo lớn nhất của tất cả cặp mảng với arr[i] ≥ arr[j] trong C++

Trong bài toán này, cho một mảng n phần tử. Nhiệm vụ: viết chương trình tìm giá trị modulo lớn nhất của tất cả các cặp mảng nơi arr[i] ≥ arr[j].

Ví dụ minh họa

Đầu vào: arr[] = {3, 5, 9}

Đầu ra: 4

Giải thích:

Tất cả các cặp arr[i] và arr[j]:
5, 3  => 5%3 = 2
9, 3  => 9%3 = 0
9, 5  => 9%5 = 4

Phương pháp giải

Cách đơn giản: Hai vòng lặp lồng nhau, tìm modulo mọi cặp. Độ phức tạp O(n²) - không hiệu quả.

Cách tối ưu trên mảng đã sắp xếp:

1. Sắp xếp mảng
2. Với mỗi phần tử arr[j], tìm các bội số x của arr[j] cho đến khi vượt quá phần tử lớn nhất
3. Tìm arr[i] < x, tính arr[i] % arr[j], cập nhật maxModulo

Minh họa thuật toán

arr = {3, 5, 9}
arr[j] = 3, j = 0, x = {6, 9}
  x = 6: arr[i] = 5, 5%3 = 2, maxModulo = 2
  x = 9: arr[i] = 9, 9%3 = 0, maxModulo = 2
arr[j] = 5, j = 1, x = {10}
  x = 10: arr[i] = 9, 9%5 = 4, maxModulo = 4

Chương trình C++

#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);
}

Kết quả

The maximum modulo of all pairs is 4

Độ phức tạp

• Thời gian: O(n log n + n log max_value)
• Không gian: O(1)