ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে যাকে 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
আকারের একটি অ্যারে অপ সংজ্ঞায়িত করুন -
ret :=0
-
আরম্ভ করার জন্য i :=0, যখন i <সংখ্যার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
যদি i - 1>=0, তাহলে −
-
op[i] :=op[i] + op[i - 1]
-
-
যদি (সংখ্যা[i] + op[i]) এবং 1 অ-শূন্য হয়, তাহলে −
-
(1 দ্বারা op[i] বাড়ান)
-
(রেট 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
