समस्या कथन
सम लंबाई की बाइनरी स्ट्रिंग और 0 और 1 की समान संख्या को देखते हुए। स्ट्रिंग को वैकल्पिक बनाने के लिए स्वैप की न्यूनतम संख्या क्या है? यदि कोई दो क्रमागत तत्व समान नहीं हैं तो एक बाइनरी स्ट्रिंग बारी-बारी से होती है
उदाहरण
अगर str =11110000 तो 2 स्वैप की आवश्यकता है।
एल्गोरिदम
- विषम स्थिति और स्ट्रिंग की सम स्थिति पर शून्यों की संख्या गिनें। उनकी गिनती क्रमशः विषम शून्य और सम शून्य हो
- विषम स्थिति और स्ट्रिंग की सम स्थिति पर संख्याओं की गणना करें। मान लीजिए कि उनकी संख्या क्रमशः विषम हैOneCnt और यहां तक किOneCnt
- हम हमेशा 1 को 0 के साथ स्वैप करेंगे। इसलिए हम सिर्फ यह जांचते हैं कि क्या हमारी वैकल्पिक स्ट्रिंग 0 से शुरू होती है तो स्वैप की संख्या न्यूनतम (ईवनज़ीरोसेंट, ऑडऑनसीएनटी) है और यदि हमारी वैकल्पिक स्ट्रिंग 1 से शुरू होती है तो स्वैप की संख्या है मिनट (समवन, विषम ज़ीरोसेंट)। उत्तर इन दोनों में से एक मिनट है
उदाहरण
#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
