ধরুন আমাদের একটি অ্যারে A আছে। এতে শুধুমাত্র 0s এবং 1s রয়েছে, এখানে একটি K-বিট ফ্লিপে রয়েছে K দৈর্ঘ্যের একটি (সংলগ্ন) সাবয়ারে বেছে নেওয়া এবং একই সাথে সাবয়ারে n বিটগুলিকে উল্টানো। আমাদের কে-বিট ফ্লিপগুলির ন্যূনতম সংখ্যা খুঁজে বের করতে হবে যাতে অ্যারেতে 0 না থাকে। যদি এমন কোন সম্ভাবনা না থাকে, তাহলে -1 রিটার্ন করুন।
সুতরাং, যদি ইনপুটটি [0,0,0,1,0,1,1,0] এবং K =3 এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমাদের প্রথম চেষ্টায় তিনবার অপারেশন করতে হবে। A[0] থেকে A[3] ফ্লিপ করুন, অ্যারে হবে [1,1,1,1,0,1,1,0], দ্বিতীয় রানে A[4] থেকে A[6] ফ্লিপ করুন, অ্যারে হবে [1,1,1,1,1,0,0,0], এবং 3য় চালে A[5] থেকে A[7] তে, অ্যারে হবে [1,1,1,1,1] ,1,1,1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A
এর আকার -
n
আকারের একটি অ্যারে মুভ সংজ্ঞায়িত করুন -
কাউন্টার :=0
-
আরম্ভ করার জন্য i :=0, যখন i + K <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
-
যদি i> 0, তাহলে −
-
moves[i] :=moves[i] + moves[i - 1]
-
-
যদি না হয় ((moves[i] mod 2) + A[i]) mod 2 অ-শূন্য, তাহলে −
-
moves[i] :=moves[i] + 1
-
i + K
-
সরানো [i + K] - =1
-
-
(1 দ্বারা কাউন্টার বাড়ান)
-
-
-
i
করুন -
যদি i> 0, তাহলে −
-
moves[i] :=moves[i] + moves[i - 1]
-
-
যদি না হয় ((moves[i] mod 2) + A[i]) mod 2 অ-শূন্য, তাহলে −
-
রিটার্ন -1
-
-
-
রিটার্ন কাউন্টার
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
আউটপুট
#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 i;
int counter = 0;
for (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 (; i < n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2))
return -1;
}
return counter;
}
};
main(){
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << (ob.minKBitFlips(v, 3));
} ইনপুট
{0,0,0,1,0,1,1,0}, 3 আউটপুট
3
