समस्या विवरण
एक बाइनरी स्ट्रिंग दी गई है जिसमें हम बाएं भाग में सभी 1s और दाएं भाग में सभी 0s को फ्लिप कर सकते हैं। कार्य सभी 1s को बाएं और सभी 0s को दाएं करने के लिए आवश्यक न्यूनतम फ्लिप्स की गणना करना है।
उदाहरण
दी गई बाइनरी स्ट्रिंग 0010101 है। इस स्ट्रिंग में 3 1-बिट्स और 4 0-बिट्स हैं। हमें नीचे दिखाए अनुसार सभी 1s को बाएं और सभी 0s को दाएं करने के लिए हाइलाइट किए गए 4 बिट्स को फ्लिप करना होगा:
0010101
फ्लिप करने के बाद स्ट्रिंग बनेगी:
1110000
एल्गोरिदम
- स्ट्रिंग को बाएं से दाएं ट्रैवर्स करें और सभी 0s को 1s में बदलने के लिए आवश्यक फ्लिप्स की संख्या गिनें।
- स्ट्रिंग को दाएं से बाएं ट्रैवर्स करें और सभी 1s को 0s में बदलने के लिए आवश्यक फ्लिप्स की संख्या गिनें।
- बिट्स के बीच सभी पोजीशन्स को ट्रैवर्स करें और (0s फ्लिप्स + 1s फ्लिप्स) का न्यूनतम मान ढूंढें।
उदाहरण
#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
