সমস্যা বিবৃতি
একটি বাইনারি স্ট্রিং দেওয়া হয়েছে যাতে আমরা সমস্ত 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