C++での特定の配列のarr[i]％arr[j]の最大値

この問題では、n個の要素の配列が与えられます。私たちのタスクは、特定の配列のarr [i]％arr[j]の最大値を見つけるプログラムを作成することです。

したがって、基本的には、配列の2つの要素を分割しながら、最大の余りの値を見つける必要があります。

問題を理解するために例を見てみましょう

入力 −配列{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になるというロジックを使用することです。そして、配列のすべての要素のうち、最大2つの要素を取得すると、結果は最大になります。このために、配列を並べ替えてから、最後と最後から2番目の要素を繰り返して結果を提供します。

例

ソリューションの実装を説明するプログラム

#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