बाइनरी स्ट्रिंग को "ab" मुक्त बनाने के लिए आवश्यक संक्रियाओं की गणना करने का C++ प्रोग्राम

समस्या विवरण

हमें एक स्ट्रिंग दी गई है जिसमें "ab" पैटर्न हो सकता है। लक्ष्य "ab" को हटाने/मिटाने के लिए आवश्यक संक्रियाओं की संख्या ज्ञात करना है। प्रत्येक संक्रिया में "ab" को "bba" से प्रतिस्थापित किया जाता है। प्रक्रिया तब तक चलती है जब तक स्ट्रिंग "ab" मुक्त न हो जाए।

उदाहरण

इनपुट: str = "ababaa"

आउटपुट: 4

व्याख्या:

1. "ababaa" → "bbaabaa" (पहला "ab" प्रतिस्थापित)
2. "bbaabaa" → "bbabbaaa" (दूसरा "ab" प्रतिस्थापित)
3. "bbabbaaa" → "bbbbaaaa" (तीसरा "ab" प्रतिस्थापित)
4. "bbbbaaaa" → "ab" मुक्त, कुल 4 संक्रियाएँ

इनपुट: str = "abaa"

आउटपुट: 1

दृष्टिकोण

स्ट्रिंग को दाएँ से बाएँ पार करें। प्रत्येक 'b' के लिए एक काउंटर बढ़ाएँ। प्रत्येक 'a' के लिए, वर्तमान काउंटर मान को उत्तर में जोड़ें और काउंटर को दोगुना करें (क्योंकि प्रत्येक 'b' भविष्य के 'a' के लिए एक नया "ab" बनाएगा)।

एल्गोरिदम

1. स्ट्रिंग लें और लंबाई की गणना करें
2. प्रारंभिक count = 0, total = 0
3. दाएँ से बाएँ लूप करें (इंडेक्स len-1 से 0):
   • यदि arr[i] == 'a': count += total; total *= 2
   • अन्यथा (यह 'b' है): total++
4. count लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int operations_ab_free(string str, int len) {
    int count = 0;
    int total = 0;
    
    for (int i = len - 1; i >= 0; i--) {
        if (str[i] == 'a') {
            count += total;
            total *= 2;
        } else {
            total++;
        }
    }
    return count;
}

int main() {
    string str = "ababaa";
    int length = str.length();
    cout << "Count: " << operations_ab_free(str, length) << endl;
    return 0;
}

आउटपुट

Count: 4