একটি বাইনারি স্ট্রিং (শুধু ০ এবং ১) দেওয়া থাকলে, '১' দিয়ে শুরু এবং '১' দিয়ে শেষ হওয়া সাবস্ট্রিংগুলোর সংখ্যা গণনা করতে হবে।
ইনপুট-১
N = 5, str = "11101"
আউটপুট
6
ব্যাখ্যা
সাবস্ট্রিংগুলো: {'11', '111', '1110', '11101', '1101', '101'}।
ইনপুট-২
N = 4, str = "0011"
আউটপুট
1
সমাধানের পদ্ধতি
এটি হ্যান্ডশেক সমস্যার মতো। স্ট্রিংয়ে মোট কতগুলো '১' আছে সেটা গণনা করুন। মোট '১' = c হলে, সাবস্ট্রিং সংখ্যা = c*(c-1)/2।
- স্ট্রিং লেন্থ N এবং স্ট্রিং ইনপুট নিন।
countSubstring(int N, string s)ফাংশন কাউন্ট রিটার্ন করবে।- স্ট্রিং ট্রাভার্স করে '১'-এর সংখ্যা গণনা করুন।
- ফর্মুলা `count*(count-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
