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