C++ में बाइनरी स्ट्रिंग को अल्टरनेटिंग बनाने के लिए न्यूनतम स्वैप

समस्या कथन

सम लंबाई की एक बाइनरी स्ट्रिंग और समान संख्या में 0s और 1s दी गई है। स्ट्रिंग को अल्टरनेटिंग बनाने के लिए न्यूनतम स्वैप की संख्या क्या है? एक बाइनरी स्ट्रिंग अल्टरनेटिंग होती है यदि कोई दो क्रमागत एलिमेंट्स समान नहीं हैं

उदाहरण

यदि str = 11110000 तो 2 स्वैप आवश्यक हैं।

एल्गोरिदम

स्ट्रिंग में ऑड पोजीशन और इवन पोजीशन पर जीरो की संख्या गिनें। मान लें कि उनकी गिनती oddZeroCnt और evenZeroCnt है
स्ट्रिंग में ऑड पोजीशन और इवन पोजीशन पर वन की संख्या गिनें। मान लें कि उनकी गिनती oddOneCnt और evenOneCnt है
हम हमेशा 1 को 0 से स्वैप करेंगे। इसलिए हम सिर्फ जांचते हैं कि यदि हमारी अल्टरनेटिंग स्ट्रिंग 0 से शुरू होती है तो स्वैप की संख्या min (evenZeroCnt, oddOneCnt) है और यदि हमारी अल्टरनेटिंग स्ट्रिंग 1 से शुरू होती है तो स्वैप की संख्या min (evenOneCnt, oddZeroCnt) है। उत्तर इन दोनों का मिनिमम है

उदाहरण

#include 
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