इस लेख में, हम सी ++ का उपयोग करके उन सबएरे की संख्या खोजने की समस्या को हल करेंगे जिनके अधिकतम और न्यूनतम तत्व समान हैं। यहाँ समस्या का उदाहरण दिया गया है -
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same. समाधान खोजने के लिए दृष्टिकोण
उदाहरणों को देखते हुए, हम कह सकते हैं कि सरणी के आकार के बराबर न्यूनतम और अधिकतम तत्वों के साथ न्यूनतम संख्या में उपसरणियां बनाई जा सकती हैं। यदि समान क्रमागत संख्याएँ हों तो उपसरणियों की संख्या अधिक हो सकती है।
इसलिए हम प्रत्येक तत्व के माध्यम से जाने का एक दृष्टिकोण लागू कर सकते हैं और जांच सकते हैं कि इसकी लगातार संख्याएं समान हैं या नहीं और लगातार संख्याएं समान होने पर वृद्धि की गणना करें, और यदि कोई अलग संख्या मिलती है तो आंतरिक लूप तोड़ दें।
परिणाम चर हर बार आंतरिक लूप के समाप्त होने या टूटने पर परिणाम चर को बढ़ाता है और अंत में परिणाम चर से परिणाम दिखाता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count =0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i]==a[j])
count++;
else
break;
}
result+=count;
count =0;
}
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} आउटपुट
Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n2).
उपरोक्त कोड की व्याख्या
इस कोड में, हम एरे के आकार को स्टोर करने के लिए वेरिएबल n ले रहे हैं, परिणाम =n, क्योंकि न्यूनतम n सबएरे बनाए जा सकते हैं और समान संख्याओं की गिनती रखने के लिए गिना जा सकता है।
बाहरी लूप का उपयोग प्रत्येक तत्व को एक सरणी में संसाधित करने के लिए किया जाता है। इनर लूप का उपयोग यह पता लगाने के लिए किया जाता है कि इंडेक्स एलिमेंट के बाद कितनी लगातार संख्याएँ समान हैं और हर बार इनर लूप के समाप्त होने पर काउंट वेरिएबल के साथ रिजल्ट वेरिएबल को बढ़ाता है। अंत में परिणाम चर में संग्रहीत आउटपुट दिखा रहा है।
कुशल तरीका
इस दृष्टिकोण में, हम प्रत्येक तत्व के माध्यम से जा रहे हैं, और प्रत्येक तत्व के लिए, हम खोज रहे हैं कि कितनी लगातार समान संख्याएं हैं। प्रत्येक समान संख्या के लिए, हम गणना चर को बढ़ा रहे हैं, और जब अलग-अलग संख्याएँ पाई जाती हैं, तो गिनती की सहायता से, हम यह पता लगा रहे हैं कि "n =n*(n+1) सूत्र का उपयोग करके कितने उप-सरणी बनाए जा सकते हैं। /2" और इस सूत्र के उत्तर के साथ परिणाम चर को बढ़ाना।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count =1,temp=a[0];
for (int i = 1; i < n; i++) {
if (temp==a[i]){
count++;
}
else{
temp=a[i];
result = result + (count*(count+1)/2);
count=1;
}
}
result = result + (count*(count+1)/2);
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
} आउटपुट
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
उपरोक्त कोड की व्याख्या
इस कोड में, हम अस्थायी चर में सरणी के 0 वें सूचकांक को संग्रहीत करते हैं और सूचकांक 1 के साथ लूप शुरू करते हैं। हम जांचते हैं कि क्या अस्थायी चर वर्तमान सूचकांक में तत्व के बराबर है और समान संख्या के लिए 1 से वृद्धि हुई है। यदि अस्थायी चर सूचकांक तत्व के बराबर नहीं है, तो हम उपसरणियों के संयोजन पाते हैं जो समान संख्याओं की गणना से बनाए जा सकते हैं और परिणाम को परिणाम चर में संग्रहीत कर सकते हैं। हम अस्थायी मान को वर्तमान इंडेक्स रीसेटिंग काउंट में 1 में बदलते हैं। अंत में, हम परिणाम चर में संग्रहीत उत्तर दिखा रहे हैं।
निष्कर्ष
इस लेख में, हम उन उपसरणियों की संख्या ज्ञात करने के लिए एक समस्या का समाधान करते हैं जिनके न्यूनतम और अधिकतम तत्व समान हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।