সমস্যা বিবৃতি
একটি বাইনারি স্ট্রিং দেওয়া হয়েছে যাতে আমরা সমস্ত 1 এর বাম অংশে এবং সমস্ত 0 এর ডান অংশে ফ্লিপ করতে পারি। কাজটি হল ন্যূনতম ফ্লিপগুলি গণনা করা যা সমস্ত 1 এর বাম দিকে এবং সমস্ত 0 ডানে তৈরি করতে হয়
উদাহরণ
দেওয়া বাইনারি স্ট্রিং হল 0010101। এই স্ট্রিংটিতে 3 1-বিট এবং 4 0-বিট রয়েছে। নীচে দেখানো হিসাবে −
সমস্ত 1 বাম এবং সমস্ত 0 ডানে করার জন্য আমাদের হাইলাইট করা 4 বিটগুলি ফ্লিপ করতে হবে।0010101
ফ্লিপ করার পর স্ট্রিং −
হয়ে যাবে1110000
অ্যালগরিদম
- বাম থেকে ডানে স্ট্রিংটি অতিক্রম করুন এবং সমস্ত 0 কে 1'তে রূপান্তর করতে প্রয়োজনীয় ফ্লিপের সংখ্যা গণনা করুন৷
- ডান থেকে বামে স্ট্রিংটি অতিক্রম করুন এবং 1 থেকে 0 এর সমস্ত কভার করার জন্য প্রয়োজনীয় ফ্লিপের সংখ্যা গণনা করুন
- বিটগুলির মধ্যে সমস্ত অবস্থানের মধ্য দিয়ে অতিক্রম করুন এবং (0 এর ফ্লিপ + 1 এর ফ্লিপ) এর ন্যূনতম মান খুঁজুন
উদাহরণ
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
} আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMinimum flips: 4
