ধরা যাক আমরা স্ট্রিং '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, স্ট্রিং 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.
