সমস্যা বিবরণ
একটি বাইনারি স্ট্রিং দেওয়া আছে যেটি আমরা বাম অংশে সব ১ এবং ডান অংশে সব ০ ফ্লিপ করতে পারি। টাস্ক হলো মিনিমাম ফ্লিপ বের করা যাতে সব ১ বামে এবং সব ০ ডানে থাকে।
উদাহরণ
দেওয়া বাইনারি স্ট্রিং: 0010101। এখানে ৩টি ১-বিট এবং ৪টি ০-বিট। হাইলাইটেড ৪টি বিট ফ্লিপ করলে সব ১ বামে এবং সব ০ ডানে চলে আসবে:
0010101
ফ্লিপ করার পর স্ট্রিং হবে:
1110000
অ্যালগরিদম
- স্ট্রিং বাম থেকে ডানে ট্রাভার্স করে সব ০ কে ১-তে কনভার্ট করার ফ্লিপ সংখ্যা ক্যালকুলেট করুন।
- স্ট্রিং ডান থেকে বাম ট্রাভার্স করে সব ১ কে ০-তে কনভার্ট করার ফ্লিপ সংখ্যা ক্যালকুলেট করুন।
- বিটগুলোর মাঝপথের সব পজিশন ট্রাভার্স করে (০'র ফ্লিপ + ১'র ফ্লিপ)-র মিনিমাম ভ্যালু বের করুন।
উদাহরণ
#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
