Python प्रोग्राम - बाइनरी स्ट्रिंग में सभी 1 वाले सबस्ट्रिंग की गिनती

एक बाइनरी स्ट्रिंग s दी गई है। हमें उन सबस्ट्रिंग की संख्या खोजनी है जिनमें केवल "1" हों। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9+7 से मोड करें।

उदाहरण

इनपुट: s = "100111"

आउटपुट: 7

व्याख्या: केवल "1" वाले सबस्ट्रिंग हैं ["1", "1", "1", "1", "11", "11", "111"]।

एल्गोरिदम

1. a := 0 (वर्तमान लगातार 1 की लंबाई)
2. count := 0
3. i 0 से len(s) - 1 तक:
   • यदि s[i] == "0": a := 0
   • अन्यथा:
     • a := a + 1
     • count := count + a
4. count लौटाएं

Python कार्यान्वयन

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

इनपुट/आउटपुट

Input: "100111"
Output: 7

व्याख्या: जब हम लगातार 1 देखते हैं, तो प्रत्येक नया 1 पिछले सभी सबस्ट्रिंग को बढ़ाता है और एक नया सबस्ट्रिंग बनाता है। इसलिए काउंट में वर्तमान लंबाई a जोड़ते हैं।