Chúng ta được cho với một mảng số Arr []. Mục đích là để đếm số lượng các cặp có hiệu số bằng hiệu số tối đa của tất cả các cặp có thể có. Số cặp (i! =J) và arr [x] - arr [y] là tối đa có thể.
Chúng ta sẽ thực hiện điều này bằng cách tìm ra sự khác biệt lớn nhất trong đó (i! =J). Và lưu trữ dưới dạng maxdiff. Sau đó, đếm tất cả các cặp có chênh lệch =maxdiff.
Hãy cùng hiểu với các ví dụ.
Đầu vào - arr [] ={1,2,3,2,4,1,5}
Đầu ra - Số cách chọn cặp có chênh lệch tối đa - 2
Giải thích -
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.
Đầu vào - arr [] ={2,4,2,4}
Đầu ra - Số cách chọn cặp có chênh lệch tối đa - 4
Giải thích -
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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với các số ngẫu nhiên.
-
Lấy một biến N lưu trữ độ dài của Arr [].
-
Hàm countPairs (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về cách chọn các cặp có hiệu số bằng hiệu số tối đa.
-
Lấy số lượng biến ban đầu là 0 cho số cách.
-
Lấy biến khác biệt làm hiệu của mỗi cặp.
-
Lấy biến maxdiff làm hiệu số tối đa của tất cả các cặp.
-
Tìm các giá trị lớn nhất và nhỏ nhất từ mảng và lưu trữ trong maxx và mini tương ứng
-
Bây giờ maxdiff sẽ là maxx-mini.
-
Traverse mảng sử dụng hai vòng lặp for cho mỗi phần tử của cặp.
-
Vòng lặp bên ngoài từ 0 <=i
-
Tính diff =arr [i] -arr [j] hoặc arr [j] -arr [i] được tính là riêng biệt. Nếu số gia tăng diff ==maxdiff vì cặp này có chênh lệch tối đa.
-
Ở cuối tất cả các vòng đếm sẽ có tổng số cặp thỏa mãn điều kiện.
-
Trả lại kết quả là số lượng.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
No. of ways of choosing pair with maximum difference : 4