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]

알고리즘의 기능을 보여주는 이 솔루션을 사용하여 예제를 해결해 보겠습니다.

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