C ++中给定数组的arr [i]％arr [j]的最大值

在这个问题中，我们得到了n个元素的数组。我们的任务是创建一个程序，该程序将为给定数组找到arr [i]％arr [j]的最大值。

因此，基本上，我们需要在分割数组的两个元素时找到最大余数的值。

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

输入-数组{3，6，9，2，1}

输出-6

解释-

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
Out the above remainders the maximum is 6.

因此，找到解决方案的直接方法是计算每对对的余数，然后找到所有对中的最大值。但是这种方法无效，因为它的时间复杂度约为n ²。

因此，一种有效的解决方案将使用以下逻辑：当y> x时x％y的值将为最大值，而余数将为x。在数组的所有元素中，如果我们采用两个最大元素，那么结果将是最大。为此，我们将对数组进行排序，然后迭代倒数第二个元素以提供结果。

示例

该程序说明了我们解决方案的实施情况，

#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<<"The maximum remainder on dividing two elements of the array is "<<maxRemainder(arr, n);
   return 0;
}

输出结果

The maximum remainder on dividing two elements of the array is 6