ধরুন আমাদের একটি বাইনারি স্ট্রিং আছে এবং আমরা যেকোনো দুটি বিট অদলবদল করতে পারি। আমাদের ন্যূনতম সংখ্যক অদলবদল করতে হবে যা সমস্ত 1গুলিকে একত্রে গোষ্ঠীভুক্ত করতে হবে৷
সুতরাং, যদি ইনপুটটি s ="0111001" এর মতো হয়, তাহলে আউটপুট হবে 1, কারণ আমরা এই অদলবদলগুলি সম্পাদন করতে পারি:0111001 -> 1111000৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ডেটা :=প্রদত্ত বাইনারি স্ট্রিং থেকে 0s এবং 1s এর একটি তালিকা
- একটি সেট করুন :=0, n:=ডেটা অ্যারের দৈর্ঘ্য
- n আকারের একটি অ্যারের যোগফল তৈরি করুন এবং এটি 0 দিয়ে পূরণ করুন, যোগফল [0] :=ডেটা[0] সেট করুন
- এক :=এক + ডেটা[0]
- আমি 1 থেকে n – 1
- পরিসরে
- summ[i] :=summ[i - 1] + ডেটা[i]
- এক :=এক + ডেটা[i]
- উত্তর :=এক
- বাম :=0, ডানে :=এক – ১
- যখন ডানে
- যদি বাঁদিকে 0 হয়, তাহলে temp :=summ[right], অন্যথায় temp :=summ[right] – summ[left - 1]
- উত্তর :=সর্বনিম্ন উত্তর, এক – অস্থায়ী
- ডান ও বাম 1 দ্বারা বাড়ান
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
class Solution(object): def solve(self, s): data = list(map(int, list(s))) 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() s = "0111001" print(ob.solve(s))
ইনপুট
"0111001"
আউটপুট
1
