हमें एक सरणी arr[] दी गई है जिसमें पूर्णांक हैं। लक्ष्य arr[] के उन सभी सबएरे की गिनती करना है जिनमें प्रत्येक में विशिष्ट तत्वों की संख्या मूल सरणी में विशिष्ट तत्वों की संख्या के समान हो। यदि मूल सरणी [1,1,2,3] है तो सबएरे होंगे [1,2,3] और [1,1,2,3]।
मूल सरणी में कुल विशिष्ट तत्व 3 हैं। दोनों सबएरे में कुल विशिष्ट तत्व भी 3 हैं।
उदाहरण सहित समझ
इनपुट - arr[] = {1,2,1,2,3,4,2 };
आउटपुट - मूल सरणी के समान कुल विशिष्ट तत्वों वाले सबएरे की संख्या: 6
व्याख्या - arr[] में विशिष्ट तत्व 4 हैं (1,2,3,4)। समान संख्या में विशिष्ट तत्वों वाले सबएरे हैं: (बाएं से दाएं विशिष्ट गिनें)
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2]
इनपुट - arr[] = {8,7,5,6,10 };
आउटपुट - मूल सरणी के समान कुल विशिष्ट तत्वों वाले सबएरे की संख्या: 1
व्याख्या - arr[] में विशिष्ट तत्व 5 हैं (5,6,7,8,10)। समान संख्या में विशिष्ट तत्वों वाले सबएरे हैं: [8,7,6,5,10]. केवल 1।
प्रोग्राम में उपयोग किया गया दृष्टिकोण
- पूर्णांक संख्याओं की एक सरणी
arr[]लें और सरणी का आकार गणना करें। - फंक्शन
sub_distinct(int arr[], int size)सरणी लेता है और लगातार तत्वों में 1 का अंतर वाले सबएरे की गिनती लौटाता है। - अस्थायी चर
countऔर चरrightऔरleftलें। - यादृच्छिक जोड़े बनाने के लिए
unordered_mapप्रकार का एक चर लें। - सरणी के आकार तक 0 से FOR लूप शुरू करें और इसके अंदर
arr[i]का मानunordered_mapमें सेट करें। - अब,
unordered_mapका आकार गणना करें औरunordered_mapको साफ़ करें। - सरणी के आकार तक 0 से FOR लूप शुरू करें।
- लूप के अंदर, WHILE शुरू करें जब तक right < size और left < unordered_map का आकार।
um[arr[right]]का मान प्री-इन्क्रीमेंट करें।- अब, जांचें यदि
um[arr[right]] == 1तोleftके मान को 1 से प्री-इन्क्रीमेंट करें। - WHILE के बाहर,
rightके मान को 1 से प्री-इन्क्रीमेंट करें। - जांचें यदि
left == unordered_map का आकारतोcount = count + size - right + 1सेट करें। um[arr[i]]को 1 से डिक्रीमेंट करें।- जांचें यदि
um[arr[i]] == 0तोleftको 1 से डिक्रीमेंट करें। - काउंट लौटाएँ।
- परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size) {
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i) {
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for (int i = 0; i < size; ++i) {
while (right < size && left < um_size) {
++um[arr[right]];
if (um[arr[right]] == 1) {
++left;
}
++right;
}
if (left == um_size) {
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0) {
--left;
}
}
return count;
}
int main() {
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of subarrays having total distinct elements same as original array are: " << sub_distinct(arr, size);
return 0;
}
आउटपुट
Count of subarrays having total distinct elements same as original array are: 1
