পাইথনে সকল ১ গ্রুপ করতে ন্যূনতম স্ব্যাপ

মনে করুন আমাদের একটি বাইনারি অ্যারে data আছে, আমাদের সকল ১-গুলো অ্যারেতে যেকোনো জায়গায় একসাথে গ্রুপ করার জন্য ন্যূনতম কতগুলো স্ব্যাপ লাগবে সেটি বের করতে হবে। উদাহরণস্বরূপ, অ্যারে যদি [1,0,1,0,1,0,0,1,1,0,1] হয়, তবে আউটপুট হবে 3, কারণ সম্ভাব্য সমাধান: [0,0,0,0,0,1,1,1,1,1,1]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

one := 0, n := length of data array সেট করুন।
n সাইজের একটি summ অ্যারে বানান এবং ০ দিয়ে পূরণ করুন, summ[0] := data[0] সেট করুন।
one := one + data[0]
for i in range 1 to n - 1
- summ[i] := summ[i - 1] + data[i]
- one := one + data[i]
ans := one
left := 0, right := one - 1
while right < n
- যদি left == 0, তবে temp := summ[right], অন্যথায় temp := summ[right] - summ[left - 1]
- ans := min(ans, one - temp)
- right এবং left ১ করে বাড়ান।
return ans

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class Solution(object):
    def minSwaps(self, 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.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

ইনপুট

[1,0,1,0,1,0,0,1,1,0,1]