পাইথনে বিকল্প মান থাকতে প্রয়োজনীয় ন্যূনতম সংখ্যক ফ্লিপ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে। এখন ধরুন আমরা s এর কিছু উপসর্গ নিতে পারি এবং এটিকে পিছনে নিয়ে যেতে পারি। তারপর, ন্যূনতম সংখ্যক অক্ষর খুঁজে বের করুন যেগুলিকে এমনভাবে ফ্লিপ করতে হবে যাতে একই মানের কোনো ধারাবাহিক অক্ষর থাকবে না।

সুতরাং, যদি ইনপুটটি s ="10010101111" এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমরা উপসর্গ "10" নিতে পারি, তারপরে এটিকে পিছনে নিয়ে যান যাতে স্ট্রিং "01010111110" হয় তারপর 3য় এবং 5ম বিটটি ডান থেকে 0 এ ফ্লিপ করুন। ("01010101010")।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=S

  এর আকার

• N :=S

  এর আকার

• s :=0

• 0 থেকে 2 * N রেঞ্জের জন্য, করুন

  • s :=s + পূর্ণসংখ্যা (S[i mod N] XOR (i AND 1))

  • যদি i>=N - 1, তাহলে

    • ans :=সর্বনিম্ন উত্তর, 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