C ++中arr [i]> = arr [j]的所有数组对的最大模

在这个问题上，我们得到一个数组，由n个元素组成。我们的任务是创建一个程序来查找所有数组对中arr [i]> = arr [j]的最大模。

在这里，我们必须找到arr [i]％arr [j]的最大值，其中arr [i]> = arr [j]。

让我们举个例子来了解这个问题，

输入− arr [] = {3，5，9}

输出-4

说明-

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

为了解决这个问题，一种简单直接的方法将运行两个嵌套循环，并为每个可能的对找到模。然后，找到它们的最大值。但是，该解决方案效率不高，因为其复杂度约为O（n ^ 2）。

一种有效的方法将应用于排序数组。我们将以以下方式应用该算法-

对于数组中的每个元素arr [j]，我们将找到是x的arr [j]倍数的值，直到找到大于数组最大元素的值为止。然后，我们将找到一个数组的所有值，使得arr [i] <x。找到arr [i]％arr [j]，然后在每次操作后将最大模值存储在maxModulo变量中。

让我们使用该解决方案解决一个示例，该示例将展示算法的功能-

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

示例

程序来查找所有数组对的最大模，其中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