हमें पूर्णांक प्रकार के तत्वों की एक सरणी दी गई है। कार्य है सरणी से जोड़े बनाना, उनके गुणनफल की गणना करना और जांचना कि वह गुणनफल उसी सरणी में मौजूद है या नहीं।
इनपुट - int arr[] = {6,2,3,1,5,10}
आउटपुट - उसी सरणी में मौजूद गुणनफल वाले जोड़ों की संख्या: 7
उपयोग किया गया दृष्टिकोण (नाइव)
- तीन नेस्टेड लूप: i, j जोड़े के लिए, k गुणनफल खोजने के लिए।
- समय जटिलता: O(n³)
कुशल दृष्टिकोण (हैश सेट)
- सभी तत्वों को अनऑर्डर्ड सेट में डालें।
- दो नेस्टेड लूप से सभी जोड़े बनाएं।
- गुणनफल की जांच सेट में O(1) में करें।
- समय जटिलता: O(n²)
उदाहरण (नाइव दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
for (int j = i+1; j < size; j++) {
int product = arr[i] * arr[j];
for (int k = 0; k < size; k++)
if (product == arr[k]) count++;
}
}
return count;
}
int main() {
int arr[] = {6,2,3,1,5,10};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of pairs whose products exist in same array are: " << product_pair(arr, size);
return 0;
} आउटपुट
Count of pairs whose products exist in same array are: 7
उदाहरण (कुशल दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size) {
unordered_set<int> s;
for (int i = 0; i < size; i++)
s.insert(arr[i]);
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 (s.find(product) != s.end()) count++;
}
}
return count;
}
int main() {
int arr[] = {6,2,3,1,5,10};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of pairs whose products exist in same array are: " << product_pair(arr, size);
return 0;
} आउटपुट
Count of pairs whose products exist in same array are: 7