पायथन में वैकल्पिक मूल्यों के लिए आवश्यक न्यूनतम संख्या में फ़्लिप खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है। अब मान लीजिए कि हम s का कुछ उपसर्ग ले सकते हैं और इसे पीछे की ओर ले जा सकते हैं। फिर, उन वर्णों की न्यूनतम संख्या ज्ञात करें जिन्हें फ़्लिप करने की आवश्यकता है ताकि समान मान के लगातार वर्ण न हों।

इसलिए, यदि इनपुट s ="10010101111" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम उपसर्ग "10" ले सकते हैं, फिर इसे पीछे की ओर ले जाएं ताकि स्ट्रिंग "01010111110" हो, फिर तीसरे और 5 वें बिट को दाएं से 0 पर फ्लिप करें। ("01010101010")।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• उत्तर:=एस का आकार

• एन:=एस का आकार

• एस:=0

• मैं के लिए 0 से 2 * एन की सीमा में, करो

  • s :=s + पूर्णांक (S[i mod N] XOR (i और 1))

  • अगर मैं>=एन -1, तो

    • उत्तर :=न्यूनतम उत्तर, s और N - s

    • s :=s - पूर्णांक (S[(i -(N - 1)) mod N]) XOR ((i - (N - 1)) और 1)

• वापसी उत्तर

उदाहरण

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

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

इनपुट

"10010101111"

आउटपुट

2