একটি বাইনারি স্ট্রিং s দেওয়া আছে। শুধু '১' ধারণকারী সাবস্ট্রিংগুলোর সংখ্যা বের করতে হবে। উত্তর বড় হলে ১০⁹+৭ মডুলো করুন।
সমস্যা উদাহরণ
ইনপুট: s = "100111"
আউটপুট: 7
ব্যাখ্যা: শুধু '১' ওয়ালা সাবস্ট্রিংগুলো: ["1", "1", "1", "1", "11", "11", "111"] (মোট ৭টি)।
সমাধানের পদ্ধতি (লিনিয়ার স্ক্যান)
a = 0(বর্তমান শুধু '১' ওয়ালা সাবস্ট্রিংয়ের দৈর্ঘ্য)count = 0- প্রতিটি ক্যারেক্টার c ∈ s এর জন্য:
- যদি
c == '0':a = 0 - অন্যথায়:
a += 1,count += a
- যদি
countরিটার্ন করুন
পাইথন কোড
def solve(s):
a = 0
count = 0
for i in range(len(s)):
if s[i] == "0":
a = 0
else:
a += 1
count += a
return count
s = "100111"
print(solve(s)) # আউটপুট: 7টেস্ট কেস
ইনপুট: "100111"
আউটপুট: 7
ব্যাখ্যা: ধারাবাহিক '১'-এর লেন্থ L হলে সেটি L*(L+1)/2 টি সাবস্ট্রিং দেয়। এই অ্যালগরিদম O(n) টাইমে এটি গণনা করে।
