मान लीजिए हमारे पास एक सरणी A है जिसमें केवल 0 और 1 हैं। एक K-बिट फ्लिप में लंबाई K का एक सन्निहित सबअरे चुनकर उसके सभी बिट्स को उल्टा करना शामिल है। हमें सरणी में कोई 0 न रहने तक आवश्यक न्यूनतम K-बिट फ्लिप की संख्या ढूंढनी है। यदि असंभव है, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट [0,0,0,1,0,1,1,0] है और K = 3, तो आउटपुट 3 होगा।
हल करने का दृष्टिकोण
हम एक लालची दृष्टिकोण का उपयोग करते हैं जिसमें फ्लिप प्रभाव को ट्रैक करने के लिए एक डिफरेंस सरणी होती है:
moves सरणी फ्लिप ऑपरेशन की शुरुआत और अंत को चिह्नित करती है
सरणी के माध्यम से बाएं से दाएं पुनरावृति करें
प्रत्येक स्थिति के लिए, अब तक के फ्लिप्स के संचयी प्रभाव की गणना करें
यदि प्रभावी बिट 0 है, तो यहां एक फ्लिप शुरू करें
पहले n-K+1 स्थितियों के बाद, शेष बिट्स की जांच करें
यदि कोई 0 रहता है, तो -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;
}
};
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
