मान लीजिए कि हमने स्ट्रिंग की लंबाई 'str' और एक स्ट्रिंग दी है। कार्य किसी दिए गए बाइनरी स्ट्रिंग में '1' से शुरू होने वाले और '1' के साथ समाप्त होने वाले सबस्ट्रिंग की संख्या की गणना करना है। एक बाइनरी स्ट्रिंग में केवल '1' और '0' होता है। उदाहरण के लिए,
इनपुट-1 -
N = 5 str = ‘11101’
आउटपुट -
6
स्पष्टीकरण - दिए गए बाइनरी स्ट्रिंग में, हमारे पास 6 सबस्ट्रिंग हैं जो '1' से शुरू होती हैं और '1' से समाप्त होती हैं। इन सबस्ट्रिंग के सेट {'11', '111', '1110', '11101', '1101', '101'} हैं।
इनपुट-1 -
N = 4 str = ‘0011’
आउटपुट -
1
स्पष्टीकरण -
दिए गए बाइनरी स्ट्रिंग में हमारे पास 1 सबस्ट्रिंग है जो '1' से शुरू होती है और '1' से समाप्त होती है। इन सबस्ट्रिंग्स का सेट सिंगलटन सेट है यानी {'11'}।
इस समस्या को हल करने के लिए इस्तेमाल किया जाने वाला तरीका
दिए गए स्ट्रिंग के लिए, हमें उन सबस्ट्रिंग की संख्या गिननी होगी जो '1' से शुरू होती हैं और '1' से समाप्त होती हैं। समस्या प्रसिद्ध हैंडशेक समस्या के समान है जिसमें हमें 'n' लोगों की पार्टी में हैंडशेक की संख्या गिननी होती है।
यदि हम दिए गए स्ट्रिंग में 1 की संख्या की गणना करते हैं, तो हम सबस्ट्रिंग का सेट ढूंढ सकते हैं जो '1' से शुरू होता है और '1' पर समाप्त होता है।
-
इनपुट एन लंबाई की एक स्ट्रिंग लें।
-
एक पूर्णांक फ़ंक्शन countSubstring(int N, string s) स्ट्रिंग की लंबाई और एक स्ट्रिंग को इनपुट के रूप में लेता है और सभी सबस्ट्रिंग की गिनती देता है जो '1' से शुरू होता है और '1' के साथ समाप्त होता है।
-
पूरी स्ट्रिंग पर पुनरावृति करें और संख्या गिनें। स्ट्रिंग में '1' का।
-
संख्या गिनें। दिए गए स्ट्रिंग में n*(n-1)/2 द्वारा सबस्ट्रिंग (जोड़ी) का।
-
n*(n-1)/2 का परिणाम लौटाएं।
उदाहरण
#include<iostream>
using namespace std;
int countSubstring(int N, string s){
int count=0;
for(int i=0; s[i]!= '\0'; ++i){
if( s[i]== '1' )
count++;
}
return count*(count-1)/2;
}
int main() {
int N=5;
string str= "11101";
cout<< countSubstring(N,str)<<endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड को चलाएंगे तो यह आउटपुट को इस रूप में प्रिंट करेगा,
6
चूंकि दी गई स्ट्रिंग में '1' की संख्या '4' है, यानी गिनती =4, '1' से शुरू होने वाले और '1' से समाप्त होने वाले सबस्ट्रिंग की कुल संख्या है, 4*(4-1)/2 =6.