সমস্যা বিবৃতি
জোড় দৈর্ঘ্যের একটি বাইনারি স্ট্রিং এবং 0 এবং 1 এর সমান সংখ্যা দেওয়া হয়েছে। স্ট্রিংকে অল্টারনেটিং করার জন্য সর্বনিম্ন কতগুলি অদলবদল করতে হবে? একটি বাইনারি স্ট্রিং বিকল্প হয় যদি কোনো দুটি পরপর উপাদান সমান না হয়
উদাহরণ
যদি str =11110000 হয় তাহলে 2টি অদলবদল প্রয়োজন।
অ্যালগরিদম
- বিজোড় অবস্থানে এবং স্ট্রিংয়ের জোড় অবস্থানে শূন্যের সংখ্যা গণনা করুন। তাদের গণনা যথাক্রমে oddZeroCnt এবং evenZeroCnt হতে দিন
- স্ট্রিং এর বিজোড় অবস্থান এবং জোড় অবস্থানে সংখ্যা গণনা করুন। তাদের গণনা যথাক্রমে oddOneCnt এবং evenOneCnt হতে দিন
- আমরা সর্বদা একটি 0 দিয়ে একটি 1 অদলবদল করব। তাই আমরা শুধু পরীক্ষা করে দেখি আমাদের বিকল্প স্ট্রিং 0 দিয়ে শুরু হয় কিনা তারপর অদলবদলের সংখ্যা মিন (evenZeroCnt, oddOneCnt) এবং যদি আমাদের বিকল্প স্ট্রিং 1 দিয়ে শুরু হয় তাহলে অদলবদলের সংখ্যা হবে min (evenOneCnt, oddZeroCnt)। উত্তর হল এই দুটির মধ্যে মিনিমাম
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
int minSwaps = 0;
int oddZeroCnt = 0;
int evenZeroCnt = 0;
int oddOneCnt = 1;
int evenOneCnt = 1;
int n = str.length();
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
if (str[i] == '1') {
++evenOneCnt;
} else {
++evenZeroCnt;
}
} else {
if (str[i] == '1') {
++oddOneCnt;
} else {
++oddZeroCnt;
}
}
}
int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
string str = "11110000";
cout << "Minimum swaps = " << getMinSwaps(str) << endl;
return 0;
} আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেআউটপুট
Minimum swaps = 2
