मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है। हमें सभी वर्णों के साथ सबस्ट्रिंग की संख्या ज्ञात करनी है। उत्तर बहुत बड़ा हो सकता है इसलिए वापसी परिणाम मोड 10^9 + 7.
इसलिए, यदि इनपुट s ="1011010" जैसा है, तो आउटपुट 5 होगा क्योंकि 1. चार गुना "1" 2. एक बार "11"
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मी :=10^9+7
-
परिणाम:=0
-
div :=बाइनरी स्ट्रिंग को '0' का उपयोग करके विभाजित करके विभाजित करें
-
div में प्रत्येक x के लिए, करें
-
अगर x खाली है, तो अगले पुनरावृत्ति के लिए जाएं
-
परिणाम:=परिणाम + भागफल (x का आकार *(x +1 का आकार))/2
-
-
वापसी परिणाम मोड एम
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
def solve(s):
m = 10**9+7
result = 0
for x in s.split('0'):
if not x: continue
result += (len(x)*(len(x)+1)) // 2
return result % m
s = "1011010"
print(solve(s)) इनपुट
"1011010"
आउटपुट
5