हमें एक सरणी arr[] दी गई है जिसमें पूर्णांक तत्व हैं। लक्ष्य arr[] की उप-सरणियों के तत्वों से बने युग्मों की गिनती ढूंढना है जैसे कि प्रत्येक उपसरणी में केवल विशिष्ट तत्व हों। यदि सरणी [1,2,2,3,3] है तो केवल विशिष्ट तत्वों वाली उपसरणी [1,2] और [2,3] होगी। और युग्म (1,2) और (2,3) होंगे इसलिए युग्मों की गिनती 2 है।
आइए उदाहरणों से समझते हैं
इनपुट - arr[] = {1,2,5,3 }
आउटपुट - विशिष्ट तत्वों वाली उप-सरणियों से बने युग्मों की गिनती - 6
व्याख्या - विशिष्ट तत्वों वाली उपसरणियाँ हैं: [1,2,5,3], संभावित युग्म (1,2), (1,3), (1,5), (2,5), (2,3), (5,3) कुल 6 युग्म।
इनपुट - arr[] = {1,2,1,2,3}
आउटपुट - विशिष्ट तत्वों वाली उप-सरणियों से बने युग्मों की गिनती - 5
व्याख्या - विशिष्ट तत्वों वाली उपसरणियाँ हैं -
[1,2] - युग्म: (1,2) [2,1] - युग्म: (2,1) [1,2,3] - युग्म: (1,2), (2,3), (1,3) कुल युग्म: 5
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- पूर्णांक सरणी को इनपुट के रूप में लें।
- फ़ंक्शन distinct_pairs(int arr[], int size) सरणी लेता है और विशिष्ट तत्वों वाली उप-सरणियों से बने युग्मों की गिनती वापस करता है।
- प्रारंभिक गिनती 0 लें। चर start=end=0 लें।
- विंडो में तत्वों को चिह्नित करने के लिए एक वेक्टर check(size, false) लें।
- लूप WHILE शुरू करें जब तक start size से कम है
- लूप के अंदर, एक और लूप WHILE शुरू करें जब तक start size से कम है AND check[arr[start]] = 0 तब count को start - end सेट करें और check[arr[start]] को true सेट करें और start को 1 से बढ़ाएं।
- लूप WHILE शुरू करें जब तक end start से कम है AND start size के बराबर नहीं है AND check[arr[start]] = true तब check[arr[end]] = false सेट करें और end को 1 से बढ़ाएं।
- गिनती वापस करें
- परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
}
आउटपुट
Count of pairs formed by distinct element sub-arrays are: 17
