C++ में फ्लिप टू जीरो

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

उदाहरण के लिए, यदि इनपुट [1, 0, 1] है, तो आउटपुट 3 होगा। इंडेक्स 0 पर ऑपरेशन, यह [0, 1, 0] में बदल देगा, फिर इंडेक्स 1 पर [0, 0, 1], फिर इंडेक्स 2 पर [0, 0, 0]।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

n := nums का आकार
आकार n की एक सरणी op परिभाषित करें
ret := 0
i := 0 से nums के आकार - 1 तक लूप चलाएं:
- यदि i - 1 >= 0, तो op[i] := op[i] + op[i - 1]
- यदि (nums[i] + op[i]) & 1 शून्येतर है:
  - op[i]++
  - ret++
ret लौटाएं

C++ कार्यान्वयन

#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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 0, 1};
    cout << (ob.solve(v));
    return 0;
}

इनपुट

{1, 0, 1}