पायथन में बाइनरी स्ट्रिंग को तीन भागों में विभाजित करने के तरीकों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है जिसे हम 3 गैर-खाली स्ट्रिंग्स s1, s2, s3 में विभाजित कर सकते हैं जैसे कि (s1 + s2 + s3 = s)। हमें उन तरीकों की संख्या ज्ञात करनी है जिनसे s को विभाजित किया जा सकता है ताकि s1, s2, और s3 में '1' अक्षरों की संख्या समान हो। उत्तर बहुत बड़ा हो सकता है इसलिए उत्तर को 10^9+7 से मॉड्यूलो करें।

उदाहरण के लिए, यदि इनपुट है s = "11101011", तो आउटपुट 2 होगा क्योंकि हम इसे इस तरह विभाजित कर सकते हैं: "11 | 1010 | 11" और "11 | 101 | 011"।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

count := s में 1 की संख्या गिनें
m := 10^9 + 7
ans := आकार 2 का एक सरणी जिसे 0 से भरा गया है
यदि count % 3 ≠ 0, तो:
- 0 लौटाएं
अन्यथा यदि count == 0, तो:
- (nCr जहाँ n = s का आकार - 1 और r = 2) % m लौटाएं
left := 0
right := s का आकार - 1
cum_s := 0, cum_e := 0
जब cum_s ≤ count//3 या cum_e ≤ count//3:
- यदि s[left] == "1", तो cum_s := cum_s + 1
- यदि s[right] == "1", तो cum_e := cum_e + 1
- यदि cum_s == count//3, तो ans[0] := ans[0] + 1
- यदि cum_e == count//3, तो ans[1] := ans[1] + 1
- left := left + 1
- right := right - 1
(ans[0] * ans[1]) % m लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(s):
    count = s.count("1")
    m = 10**9 + 7
    ans = [0, 0]
    if count % 3 != 0:
        return 0
    elif count == 0:
        from math import comb
        return comb(len(s)-1, 2) % m
    left = 0
    right = len(s) - 1
    cum_s = 0
    cum_e = 0
    while cum_s <= count//3 or cum_e <= count//3:
        if s[left] == "1":
            cum_s += 1
        if s[right] == "1":
            cum_e += 1
        if cum_s == count//3:
            ans[0] += 1
        if cum_e == count//3:
            ans[1] += 1
        left += 1
        right -= 1
    return (ans[0] * ans[1]) % m

s = "11101011"
print(solve(s))

इनपुट

"11101011"