সমস্যা বিবরণ
সমান দৈর্ঘ্যের একটি বাইনারি স্ট্রিং দেওয়া আছে যেখানে ০ এবং ১-এর সংখ্যা সমান। স্ট্রিংকে অল্টারনেটিং (কোনো দুটি רצeinander সমান না) করার জন্য ন্যূনতম কতগুলো সোয়াপ দরকার? উদাহরণ: "11110000" এর জন্য ২টি সোয়াপ।
অ্যালগরিদম
- স্ট্রিং-এর অড্ড এবং ইভেন পজিশনে ০ এবং ১-এর সংখ্যা গণনা করুন (oddZeroCnt, evenZeroCnt, oddOneCnt, evenOneCnt)।
- স্ট্রিং যদি ০ দিয়ে শুরু হয়, তবে সোয়াপ = min(evenZeroCnt, oddOneCnt)।
- স্ট্রিং যদি ১ দিয়ে শুরু হয়, তবে সোয়াপ = min(evenOneCnt, oddZeroCnt)।
- উত্তর = উপরের দুটির মিনিমাম।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
int oddZeroCnt = 0, evenZeroCnt = 0;
int oddOneCnt = 0, evenOneCnt = 0;
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
