Mô-đun tối đa của tất cả các cặp mảng trong đó arr [i]> =arr [j] trong C ++

Trong bài toán này, chúng ta cho một mảng, có n phần tử. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm mô-đun tối đa của tất cả các cặp mảng trong đó arr [i]> =arr [j].

Ở đây, chúng ta phải tìm giá trị lớn nhất của arr [i]% arr [j] trong đó arr [i]> =arr [j].

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra - 4

Giải thích -

All possible Pairs arr[i] and arr[j],
5, 3 => 5%3 = 2
9, 3 => 9%3 = 0
9, 5 => 9%5 = 4

Để giải quyết vấn đề này, một cách tiếp cận đơn giản và trực tiếp sẽ là chạy hai vòng lặp lồng nhau và tìm mô đun cho mọi cặp có thể. Sau đó, tìm tối đa chúng. Tuy nhiên, giải pháp này sẽ không hiệu quả vì độ phức tạp của nó sẽ là bậc O (n ^ 2).

Một cách tiếp cận hiệu quả sẽ được áp dụng trên mảng đã sắp xếp. Thuật toán sẽ được chúng tôi áp dụng theo cách sau -

Với mọi phần tử arr [j] trong mảng, chúng ta sẽ tìm các giá trị là bội số của arr [j], chẳng hạn như x cho đến khi chúng ta tìm thấy giá trị lớn hơn phần tử lớn nhất của mảng. Sau đó, chúng ta sẽ tìm tất cả các giá trị của một mảng sao cho arr [i]

Hãy giải một ví dụ bằng giải pháp này sẽ cho thấy hoạt động của thuật toán -

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

Ví dụ

Chương trình tìm mô-đun tối đa của tất cả các cặp mảng trong đó 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);
}

Đầu ra

The maximum modulo of all pairs is 4