हमें पूर्णांक प्रकार के तत्वों की एक सॉर्टेड सरणी और एक पूर्णांक चर x दिया गया है। कार्य है सरणी से जोड़े बनाना और उनके योग की गणना करके जांचना कि वह x से कम है या नहीं।
इनपुट - int arr[] = {2,7,1,0,8}, x = 8
आउटपुट - सॉर्टेड सरणी में योग x से कम वाले जोड़ों की संख्या: 4
उपयोग किया गया दृष्टिकोण (नाइव)
- सरणी इनपुट करें और आकार ज्ञात करें।
countवेरिएबल लें।- दो नेस्टेड लूप: i = 0 से size-1, j = i+1 से size-1।
- योग =
arr[i] + arr[j]जांचें यदिsum < xतो काउंट बढ़ाएं।
कुशल दृष्टिकोण (टू पॉइंटर)
सरणी सॉर्टेड होने पर टू पॉइंटर तकनीक:
left = 0, right = size-1- जब तक
left < right:- यदि
arr[left] + arr[right] < x:count += (right - left)left++
- अन्यथा
right--
- यदि
उदाहरण (नाइव दृष्टिकोण)
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x) {
int count = 0;
for (int i = 0; i < size; i++) {
for (int j = i+1; j < size; j++) {
int sum = arr[i] + arr[j];
if (sum < x) count++;
}
}
return count;
}
int main() {
int arr[] = {2,7,1,0,8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout << "Count of pairs in a sorted array whose sum is less than x are: " << pair_sum(arr, size, x);
return 0;
} आउटपुट
Count of pairs in a sorted array whose sum is less than x are: 4
उदाहरण (कुशल दृष्टिकोण)
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x) {
int left = 0, right = size - 1;
int count = 0;
while (left < right) {
if (arr[left] + arr[right] < x) {
count += (right - left);
left++;
} else {
right--;
}
}
return count;
}
int main() {
int arr[] = {2,7,1,0,8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout << "Count of pairs in a sorted array whose sum is less than x are: " << pair_sum(arr, size, x);
return 0;
} आउटपुट
Count of pairs in a sorted array whose sum is less than x are: 4