समस्या विवरण
एक सरणी A दी गई है जिसमें n विभिन्न तत्व हैं। हमें सरणी से एक जोड़ी (x, y) ढूंढनी है जिससे x और y का अंतर दिए गए अंतर d के बराबर हो। उदाहरण के लिए, यदि सरणी A = [10, 15, 26, 30, 40, 70] है और दिया गया अंतर 30 है, तो जोड़ियां (10, 40) और (30, 70) होंगी।
हल दृष्टिकोण
इस समस्या को हल करने के लिए, हम मान लेते हैं कि सरणी क्रमबद्ध है। फिर हम दो पॉइंटर्स का उपयोग करते हैं: पहला पॉइंटर 'i' पहले तत्व को इंगित करता है और दूसरा पॉइंटर 'j' दूसरे तत्व को इंगित करता है।
- यदि A[j] - A[i] अंतर d के बराबर है, तो जोड़ी प्रिंट करें और दोनों पॉइंटर्स बढ़ाएं
- यदि A[j] - A[i] < d है, तो j को बढ़ाएं
- अन्यथा i को बढ़ाएं
यह दृष्टिकोण O(n) समय जटिलता में काम करता है क्योंकि सरणी क्रमबद्ध है।
उदाहरण कोड
#include <iostream>
using namespace std;
void displayPair(int arr[], int size, int n) {
int i = 0;
int j = 1;
while (i < size && j < size) {
if (i != j && arr[j] - arr[i] == n) {
cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
i++; j++;
}
else if (arr[j] - arr[i] < n)
j++;
else
i++;
}
}
int main() {
int arr[] = {10, 15, 26, 30, 40, 70};
int size = sizeof(arr)/sizeof(arr[0]);
int n = 30;
displayPair(arr, size, n);
return 0;
}
आउटपुट
(10, 40) (30, 70)
