समस्या कथन
एक बाइनरी स्ट्रिंग को देखते हुए जिसमें हम सभी 1 को बाएं भाग में और सभी 0 को दाएं भाग में फ़्लिप कर सकते हैं। कार्य सभी 1 को बाईं ओर और सभी 0 को दाईं ओर बनाने के लिए आवश्यक न्यूनतम फ़्लिप की गणना करना है
उदाहरण
दिया गया बाइनरी स्ट्रिंग 0010101 है। इस स्ट्रिंग में 3 1-बिट्स और 4 0-बिट्स हैं। हमें सभी 1 को बाईं ओर और सभी 0 को दाईं ओर बनाने के लिए हाइलाइट किए गए 4 बिट्स को फ़्लिप करना होगा जैसा कि नीचे दिखाया गया है -
0010101
फ़्लिप करने के बाद स्ट्रिंग बन जाएगी -
1110000
एल्गोरिदम
- स्ट्रिंग को बाएं से दाएं पार करें और सभी 0 को 1 में बदलने के लिए आवश्यक फ़्लिप की संख्या की गणना करें।
- दाईं से बाईं ओर स्ट्रिंग को पार करें और सभी 1 से 0 को गुप्त करने के लिए आवश्यक फ़्लिप की संख्या की गणना करें
- बिट्स के बीच की सभी स्थितियों को पार करें और (0 के फ़्लिप + 1′s फ़्लिप) का न्यूनतम मान ज्ञात करें
उदाहरण
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Minimum flips: 4