পাইথনে বাইনারি স্ট্রিংয়ে সব ১ গোষ্ঠীবদ্ধ করার ন্যূনতম সওয়াপ সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরা যাক একটি বাইনারি স্ট্রিং আছে, সব ১ গোষ্ঠীবদ্ধ করার ন্যূনতম সওয়াপ সংখ্যা বের করতে হবে।

উদাহরণ: "10101001101" হলে আউটপুট 3, কারণ "00000111111" সম্ভব।

সমাধানের ধাপসমূহ

data := স্ট্রিং থেকে বিটের তালিকা
one := 0, n := len(data)
summ অ্যারে (আকার n, 0 দিয়ে ভরা), summ[0] = data[0], one += data[0]
i = 1 থেকে n-1 পর্যন্ত: summ[i] = summ[i-1] + data[i], one += data[i]
ans := one, left := 0, right := one - 1
যখন right < n: temp = summ[right] - (summ[left-1] যদি left>0), ans = min(ans, one - temp), left++, right++
ans ফেরত দিন।

উদাহরণ কোড

class Solution(object):
    def solve(self, data):
        data = list(map(int, list(data)))
        one = 0
        n = len(data)
        summ = [0 for i in range(n)]
        summ[0] = data[0]
        one += data[0]
        for i in range(1, n):
            summ[i] += summ[i-1] + data[i]
            one += data[i]
        ans = one
        left = 0
        right = one - 1
        while right < n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans, one - temp)
            right += 1
            left += 1
        return ans

ob = Solution()
print(ob.solve("10101001101"))

ইনপুট

"10101001101"