सी ++ में अधिकतम विशिष्ट तत्वों वाले बाद के चरणों की संख्या

हमें एक सरणी दी गई है arr[] जिसमें केवल पूर्णांक हैं। लक्ष्य गिरफ्तारी के बाद की संख्या का पता लगाना है [] जैसे कि उनके पास अधिकतम संख्या में अलग-अलग तत्व हों। यदि सरणी [4,1,2,3,4] है तो उसके बाद के दो क्रम [4,1,2,3] और [1,2,3,4] होंगे।

आइए उदाहरणों के साथ समझते हैं

इनपुट - गिरफ्तारी [] ={ 1,3,5,4,2,3,1 }

आउटपुट − अधिकतम विशिष्ट तत्वों वाले बाद के क्रमों की संख्या है − 4

स्पष्टीकरण - अधिकतम विशिष्ट तत्व 1,2,3,4 और 5 हैं। गणना 5 है। इसके बाद के परिणाम होंगे -

[ 1,3,5,4,2], [3,5,4,2,1], [5,4,2,3,1], [ 1,5,4,2,3 ]।

इनपुट - गिरफ्तारी [] ={ 5,4,2,1,3 }

आउटपुट - अधिकतम विशिष्ट तत्वों वाले बाद के क्रमों की संख्या है - 1

स्पष्टीकरण - सभी तत्व अलग हैं। बाद की संख्या 1 होगी।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

इस दृष्टिकोण में हम इस तथ्य के आधार पर अनुवर्ती पाएंगे कि यदि सभी तत्व अलग-अलग हैं तो बाद की संख्या 1 है जो कि सरणी ही है। यदि दोहराए गए तत्व हैं तो प्रत्येक दोहराया तत्व एक नए बाद का हिस्सा होगा। तो हम अलग-अलग तत्वों की आवृत्तियों का एक unordered_map बनाएंगे। फिर प्रत्येक आवृत्ति के लिए उस आवृत्ति को गिनने के लिए गुणा करें। अंत में गिनती में आवृत्तियों की कुल संख्या होती है।

• इनपुट के रूप में एक पूर्णांक सरणी arr[] लें।

• फ़ंक्शन Max_distinct_subseq(int arr[], int size) सरणी और उसका आकार लेता है और अधिकतम विशिष्ट तत्वों के साथ बाद की संख्या देता है।

• प्रारंभिक गणना को 1 के रूप में लें जैसे कि सभी तत्व अलग-अलग हैं, तो सरणी ही अधिकतम विशिष्ट तत्वों के साथ अनुवर्ती है।

• unordered_map हैश बनाएं; सभी अलग-अलग तत्वों की आवृत्तियों को संग्रहीत करने के लिए।

• लूप के लिए सरणी को पार करें और हैश[arr[i]]]++ का उपयोग करके arr[i] प्रत्येक तत्व के लिए आवृत्तियों को अपडेट करें।

• अब लूप के लिए हैश का उपयोग करके हैश को पार करें। प्रत्येक आवृत्ति के लिए यह->दूसरा(it=iterator) पिछली गणना से गुणा करें। चूँकि एक ही समय के x तत्व x भिन्न-भिन्न क्रमों का हिस्सा होंगे।

• अंत में गिनती में आवृत्तियों की कुल संख्या होती है।

• परिणाम के रूप में वापसी की गिनती।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
   int count = 1;
   unordered_map<int, int> hash;
   for (int i = 0; i < size; i++){
      hash[arr[i]]++;
   }
   for (auto it = hash.begin(); it != hash.end(); it++){
      count = count * (it->second);
   }
   return count;
}
int main(){
   int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Count of subsequences having maximum distinct elements are: 3