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