পাইথনে K-লেন্থ সাবলিস্ট ফ্লিপ করে সব আইটেম ০ করার প্রোগ্রাম

ধরুন আমাদের একটি লিস্ট আছে nums যেটিতে শুধু ০ ও ১ আছে। আরেকটি মান আছে k।

একটি অপারেশন বিবেচনা করুন যেখানে আমরা k দৈর্ঘ্যের একটি সাবলিস্ট ফ্লিপ করি—যাতে সব ১ হয়ে যায় ০ এবং সব ০ হয়ে যায় ১। nums-কে পুরো ০-তে পরিবর্তন করতে কমপক্ষে কত অপারেশন দরকার সেটি বের করতে হবে। যদি সম্ভব না হয় তবে -1 রিটার্ন করুন।

উদাহরণস্বরূপ, nums = [1,1,1,0,0,1,1,1], k = 3 হলে আউটপুট হবে 2, কারণ প্রথম তিনটি নম্বর ফ্লিপ করে ০ করতে পারি, তারপর শেষ তিনটি নম্বর ফ্লিপ করে ০ করতে পারি।

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

n := nums-এর আকার
res := 0, flipped := 0
to_conv := n আকারের লিস্ট, ০ দিয়ে ভরা
i = 0 থেকে n-1 পর্যন্ত লুপ:
- flipped := flipped XOR to_conv[i]
- cur := nums[i]
- cur := cur XOR flipped
- যদি cur == 1 হয়:
  - flipped := flipped XOR 1
  - res := res + 1
  - যদি i + k - 1 >= n হয়, তবে -1 রিটার্ন করুন
  - যদি i + k < n হয়, তবে to_conv[i + k] := 1
res রিটার্ন করুন

উদাহরণ

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        res = 0
        flipped = 0
        to_conv = [0] * n
        for i in range(n):
            flipped ^= to_conv[i]
            cur = nums[i]
            cur ^= flipped
            if cur == 1:
                flipped ^= 1
                res += 1
                if i + k - 1 >= n:
                    return -1
                if i + k < n:
                    to_conv[i + k] = 1
        return res

ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))

ইনপুট

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