ধরা যাক আপনি একটি বাইনারি স্ট্রিং "10011" দিয়েছেন। একটি বিকল্প বাইনারি স্ট্রিং তৈরি করতে, আমাদের "10101" হিসাবে ন্যূনতম 2টি অক্ষর ফ্লিপ করতে হবে৷
বিকল্প স্ট্রিং জন্য দুটি সম্ভাবনা আছে. এটি 0 বা 1 দিয়ে শুরু হবে৷ আমরা দুটি বিকল্পের জন্য পরীক্ষা করব এবং উভয়ের জন্য প্রয়োজনীয় ফ্লিপের সংখ্যা গণনা করব৷
এবং তারপর উভয়ের সর্বনিম্ন ফেরত দিন। আসুন একটি উদাহরণ দেখি।
ইনপুট
binary = "10011"
আউটপুট
2
যদি আমরা 0 দিয়ে স্ট্রিং শুরু করি, তাহলে আমাদের 3 বার ফ্লিপ করতে হবে। এবং যদি আমরা 1 দিয়ে স্ট্রিং শুরু করি, তাহলে আমাদের 2 বার উল্টাতে হবে। সর্বনিম্ন 2।
অ্যালগরিদম
- বাইনারী স্ট্রিং শুরু করুন।
- 1 দিয়ে শুরু করে বিকল্প স্ট্রিং তৈরি করতে প্রয়োজনীয় ফ্লিপগুলি গণনা করুন।
- একইভাবে 0 দিয়ে শুরু করে বিকল্প স্ট্রিং তৈরি করতে প্রয়োজনীয় ফ্লিপগুলি গণনা করুন।
- উপরের দুটি থেকে সর্বনিম্ন খুঁজুন।
- সর্বনিম্ন প্রিন্ট করুন।
বাস্তবায়ন
C++
-এ উপরের অ্যালগরিদমের বাস্তবায়ন নিচে দেওয়া হল#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
int flipCount = 0;
for (int i = 0; i < binary.length(); i++) {
if (binary[i] != expected) {
flipCount++;
}
expected = flip(expected);
}
return flipCount;
}
int main() {
string binary = "10011";
cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary, '1')) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
2
