C++-এ ফ্লিপ টু জিরো: সাফিক্স ফ্লিপ অপারেশন কম দিয়ে সব শূন্য করা

একটি বাইনারি অ্যারে দেওয়া আছে। একটি অপারেশনে index i বাছাই করলে i থেকে শেষ পর্যন্ত সব বিট ফ্লিপ হয় (০↔১)। পুরো অ্যারে শূন্য করার জন্য ন্যূনতম অপারেশন কতটি লাগবে?)

উদাহরণ

ইনপুট: [1, 0, 1]

প্রক্রিয়া:

1. Index 0 ফ্লিপ → [0, 1, 0]
2. Index 1 ফ্লিপ → [0, 0, 1]
3. Index 2 ফ্লিপ → [0, 0, 0]

আউটপুট: 3

অ্যালগরিদম (প্রিফিক্স সাম/ডিফারেন্স অ্যারে)

1. op[i] = index i-এ কতবার ফ্লিপ হয়েছে তা ট্র্যাক করুন।
2. op[i] += op[i-1] (প্রিফিক্স সাম)।
3. বর্তমান বিট = (nums[i] + op[i]) % 2।
4. যদি ১ হয়, তবে এখানে ফ্লিপ করুন: op[i]++, 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, 0);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (i > 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;
}

মূল ইনসাইট

এটি গ্রিডি অ্যালগরিদম: বাম থেকে ডানে যেতে হলে, বর্তমান বিট ১ থাকলে অবশ্যই এখানে ফ্লিপ করতে হবে, কারণ পরে ফ্লিপ করলে এই বিট আবার ১ হয়ে যাবে।