সমস্যা বিবরণ
একটি বাইনারি অ্যারে A দেওয়া থাকলে, K-বিট ফ্লিপ মানে K দৈর্ঘ্যের সংলগ্ন সাবঅ্যারে এর সব বিট ইনভার্ট করা। অ্যারেটির সব উপাদান ১ করার জন্য ন্যূনতম K-বিট ফ্লিপের সংখ্যা বের করতে হবে। অসম্ভব হলে -1 রিটার্ন করুন।
উদাহরণ
A = [0,0,0,1,0,1,1,0], K = 3 → আউটপুট = 3
সমাধান পদ্ধতি
- স্লাইডিং উইন্ডো + ডিফারেন্স আরে (Difference Array) টেকনিক ব্যবহার করা হয়।
- moves আরে দিয়ে ফ্লিপের প্রভাব ট্র্যাক করা হয়।
- প্রতিটি পজিশনে বর্তমান ফ্লিপ সংখ্যা মডুলো ২ দিয়ে বর্তমান বিট বের করা হয়।
- যদি বিট ০ হয়, তবে সেখান থেকে K দৈর্ঘ্যের ফ্লিপ করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int n = A.size();
vector<int> moves(n);
int counter = 0;
for (int i = 0; i + K <= n; i++) {
if (i > 0) moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) {
moves[i] += 1;
if (i + K < n) moves[i + K] -= 1;
counter++;
}
}
for (int i = 0; i < n; i++) {
if (i > 0) moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) return -1;
}
return counter;
}
};
int main() {
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << ob.minKBitFlips(v, 3);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {0,0,0,1,0,1,1,0}, 3
আউটপুট: 3
