সমস্যা বিবৃতি
শুধুমাত্র 0 এবং 1 সমন্বিত n পূর্ণসংখ্যাগুলির একটি অ্যারে দেওয়া হয়েছে। ন্যূনতম টগলগুলি খুঁজুন (0 থেকে 1 থেকে বা বিপরীতে স্যুইচ করুন) এমন অ্যারের প্রয়োজন যেমন অ্যারেটি বিভাজিত হয়ে যায়, অর্থাৎ, এটিতে প্রথমে 0s তারপর 1s আছে।
উদাহরণ
যদি arr[] ={1, 0, 0, 1, 1, 1, 0} তাহলে 2টি টগল প্রয়োজন, যেমন প্রথমটি এবং শেষ শূন্য টগল করুন৷
অ্যালগরিদম
- যদি আমরা প্রশ্নটি পর্যবেক্ষণ করি, তাহলে আমরা দেখতে পাব যে 0 থেকে n-1 পর্যন্ত একটি বিন্দু অবশ্যই থাকবে যেখানে সেই বিন্দু থেকে বাকি সমস্ত উপাদানে সমস্ত 0 এবং ডান থেকে বিন্দুতে সমস্ত 1'স থাকা উচিত
- যেসব সূচক এই আইন মানে না তাদের সরিয়ে দিতে হবে। ধারণা হল বাম থেকে ডানে সমস্ত 0 সেকেন্ড গণনা করা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
int zeroCnt[n + 1] = {0};
for (int i = 1; i <= n; ++i) {
if (arr[i - 1] == 0) {
zeroCnt[i] = zeroCnt[i - 1] + 1;
} else {
zeroCnt[i] = zeroCnt[i - 1];
}
}
int result = n;
for (int i = 1; i <= n; ++i) {
result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
}
return result;
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
return 0;
} যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেআউটপুট
Minimum toggles = 2
