मान लीजिए आपके पास एक बाइनरी स्ट्रिंग "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
