C++ में शून्य पर पलटें

मान लीजिए कि हमारे पास एक पूर्णांक सरणी है जिसे nums कहा जाता है और इसमें 0s और 1s होते हैं। मान लीजिए कि हमारे पास एक ऑपरेशन है जहां हम इंडेक्स i को अंकों में चुनते हैं और इंडेक्स i पर फ्लिप तत्व के साथ-साथ i के दाईं ओर सभी नंबर भी चुनते हैं। हमें सभी 0s वाले अंकों को बनाने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी होगी।

तो, अगर इनपुट [1,0,1] जैसा है, तो आउटपुट 3 होगा, इंडेक्स 0 पर ऑपरेशन, यह [0,1,0] कन्वर्ट होगा, फिर इंडेक्स 1 पर [ 0,0,1], फिर इंडेक्स 2, [0,0,0]।

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

• n :=अंकों का आकार

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

• रिट:=0

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

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

    • op[i] :=op[i] + op[i - 1]

  • अगर (nums[i] + op[i]) और 1 शून्य नहीं है, तो -

    • (op[i] को 1 से बढ़ाएं)

    • (रिटर्न 1 से बढ़ाएं)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int n = nums.size();
      vector<int> op(n);
      int ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         if (i - 1 >= 0) {
            op[i] += op[i - 1];
         }
         if ((nums[i] + op[i]) & 1) {
            op[i]++;
            ret++;
         }
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<int> v = {1,0,1};
   cout << (ob.solve(v));
}

इनपुट

{1,0,1}

आउटपुट

3