समस्या कथन
आपको n पूर्णांक और एक पूर्णांक K की एक सरणी दी गई है। कुल असंगठित युग्मों की संख्या ज्ञात कीजिए {i, j} जैसे कि |ai + aj – k| का निरपेक्ष मान। न्यूनतम संभव है जहां मैं !=j.
उदाहरण
अगर arr[ ] ={0, 4, 6, 2, 4} और k =7 तो हम निम्न 5 जोड़े बना सकते हैं जिनका न्यूनतम मान 1
है{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}
एल्गोरिदम
सभी संभावित युग्मों पर पुनरावृति करें और प्रत्येक जोड़ी के लिए हम जाँच करेंगे कि क्या (ai + aj - K) का मान हमारे वर्तमान सबसे छोटे मान से छोटा है। तो उपरोक्त शर्त के परिणाम के अनुसार हमारे पास कुल तीन मामले हैं -
- abs(ai + aj – K)> सबसे छोटा - कुछ भी न करें क्योंकि यह जोड़ी न्यूनतम संभव मान में नहीं गिना जाएगा।
- abs(ai + aj – K) =सबसे छोटा - जोड़े की संख्या में वृद्धि करें जिसके परिणामस्वरूप न्यूनतम संभव मान हो।
- abs(ai + aj – K) <सबसे छोटा - सबसे छोटा मान अपडेट करें और गिनती को 1 पर सेट करें।
उदाहरण
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getPairs(int *arr, int n, int k) {
int minValue = INT_MAX;
int pairs = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int val = abs(arr[i] + arr[j] - k); if (val < minValue) {
minValue = val;
pairs = 1;
} else if (val == minValue) {
++pairs;
}
}
}
cout << "Min value = " << minValue << endl; cout << "Total pairs = " << pairs << endl;
}
int main() {
int arr[] = {0, 4, 6, 2, 4};
int k = 7;
int n = sizeof(arr) / sizeof(arr[0]);
getPairs(arr, n, k);
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Min value= 1 Total pairs = 5