在这个问题上,我们得到一个数组,由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