मान लीजिए कि आपने एक बाइनरी स्ट्रिंग "10011" दी है। एक वैकल्पिक बाइनरी स्ट्रिंग बनाने के लिए, हमें कम से कम 2 वर्णों को "10101" के रूप में फ़्लिप करना होगा।
वैकल्पिक स्ट्रिंग के लिए दो संभावनाएं हैं। यह 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