C++ में K लगातार बिट फ़्लिप की न्यूनतम संख्या

मान लीजिए कि हमारे पास एक सरणी A है। इसमें केवल 0s और 1s हैं, यहाँ K-बिट फ्लिप में लंबाई K का एक (सन्निहित) सबअरे चुनना और साथ ही बिट्स n सबएरे को इनवर्ट करना शामिल है। हमें K-बिट फ़्लिप की न्यूनतम संख्या ज्ञात करनी होगी ताकि सरणी में कोई 0 न हो। अगर ऐसी कोई संभावना नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट [0,0,0,1,0,1,1,0] और K =3 जैसा है, तो आउटपुट 3 होगा, क्योंकि हमें पहले प्रयास में तीन बार ऑपरेशन करने की आवश्यकता है ए [0] से ए [3] फ्लिप करें, सरणी [1,1,1,1,0,1,1,0] होगी, दूसरे रन पर ए [4] से ए [6], सरणी फ्लिप करें [1,1,1,1,1,0,0,0] होगा, और तीसरी चाल में A[5] को A[7] में बदलें, सरणी [1,1,1,1,1] होगी ,1,1,1].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=A का आकार

• आकार n की सरणी चालों को परिभाषित करें

• काउंटर :=0

• इनिशियलाइज़ i :=0 के लिए, जब i + K <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • अगर मैं> 0, तो -

    • चाल [i] :=चाल[i] + चाल[i - 1]

  • यदि नहीं ((चाल [i] mod 2) + A[i]) mod 2 गैर-शून्य है, तो -

    • चाल [i] :=चाल [i] + 1

    • अगर मैं + के <एन, तो -

      • चाल [i + K] - =1

    • (काउंटर 1 से बढ़ाएं)

• i

  • अगर मैं> 0, तो -

    • चाल [i] :=चाल[i] + चाल[i - 1]

  • यदि नहीं ((चाल [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