숫자 Arr[]의 배열이 제공됩니다. 목표는 차이가 가능한 모든 쌍의 최대 차이와 같은 쌍의 수를 계산하는 것입니다. 카운트 쌍(i!=j) 및 arr[x]- arr[y]는 최대 가능합니다.
먼저 (i!=j)에서 최대 차이를 찾아 이를 수행합니다. 그리고 maxdiff로 저장합니다. 그런 다음 difference=maxdiff가 있는 모든 쌍을 계산합니다.
예를 들어 이해합시다.
입력 - arr[]={ 1,2,3,2,4,1,5 }
출력 − 차이가 최대인 쌍을 선택하는 방법의 수 − 2
설명 -
Here minimum no. is 1 and maximum number is 5, maximum difference =5-1=4 Pair 1 [ 1,2,3,2,4,1,5 ] → (1,5) difference=4 Pair 2 [ 1,2,3,2,4,1,5 ] → (1,5) difference=4 Number of pairs with difference which is maximum=2.
입력 - arr[]={ 2,4,2,4 }
출력 − 차이가 최대인 쌍을 선택하는 방법의 수 − 4
설명 -
Here minimum no. is 2 and maximum number is 4, maximum difference =4-2=2 Pair 1 [ 2,4,2,4 ] → (2,4) difference=2 Pair 2 [ 2,4,2,4 ] → (2,4) difference=2 Pair 3 [ 2,4,2,4 ] → (4,2) difference=2 Pair 4 [ 2,4,2,4 ] → (2,4) difference=2 Number of pairs with difference which is maximum=4.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
임의의 숫자로 초기화된 정수 배열 Arr[]을 사용합니다.
-
Arr[]의 길이를 저장하는 변수 N을 사용합니다.
-
countPairs(int arr[],int n) 함수는 배열의 길이를 입력으로 취하고 차이가 최대 차이와 같은 쌍을 선택하는 방법을 반환합니다.
-
방법의 수에 대해 초기 변수 개수를 0으로 간주합니다.
-
변수 diff를 각 쌍의 차이로 취하십시오.
-
모든 쌍의 최대 차이로 maxdiff 변수를 사용합니다.
-
배열에서 최대값과 최소값을 찾아 각각 maxx와 mini에 저장
-
이제 maxdiff는 maxx-mini가 됩니다.
-
쌍의 각 요소에 대해 두 개의 for 루프를 사용하여 배열을 탐색합니다.
-
0<=i
-
diff=arr[i]-arr[j] 또는 arr[j]-arr[i] 개수를 별도로 계산합니다. diff==maxdiff인 경우 이 쌍이 최대 차이를 가지므로 증분 카운트.
-
모든 루프의 끝에서 카운트는 조건을 충족하는 총 쌍 수를 갖습니다.
-
카운트를 결과로 반환합니다.
예
#include <bits/stdc++.h>
using namespace std;
int countWays(int arr[],int n){
int count = 0;
int diff;
int maxdiff=0; //making minimum as larger than any product in array
int mini,maxx;
mini=maxx=arr[0];
for (int i = 0; i < n; i++) //find minimum and maximum values{
if(arr[i]<mini)
{mini=arr[i];}
if(arr[i]>maxx)
{ maxx=arr[i]; }
}
maxdiff=maxx-mini; //this is maximum difference
//cout<<maxx<<" "<<mini;
for (int i = 0; i < n-1; i++){
for (int j = i+1; j < n; j++){
diff=arr[i]-arr[j]; //pair 1
if ( diff==maxdiff ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
diff=arr[j]-arr[i]; //pair 2
if ( diff==maxdiff ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
}
}
return count;
}
int main(){
int Arr[]={ 3, 2, 1, 1, 3 };
int N=5; //length of array
cout <<endl<< "No. of ways of choosing pair with maximum difference : "<<countWays(Arr,N);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
No. of ways of choosing pair with maximum difference : 4