C++ में बाइनरी ऐरे को पार्टीशन करने के लिए न्यूनतम टॉगल (पहले 0s फिर 1s)

समस्या कथन

केवल 0 और 1 वाले n पूर्णांकों का एक ऐरे दिया गया है। न्यूनतम टॉगल (0 से 1 या इसके विपरीत स्विच) ढूंढें ताकि ऐरे पार्टीशन हो जाए, यानी, उसमें पहले 0s फिर 1s हों।

उदाहरण

यदि arr[] = {1, 0, 0, 1, 1, 1, 0} तो 2 टॉगल आवश्यक हैं यानी पहले 1 और अंतिम 0 को टॉगल करें।

एल्गोरिदम

• यदि हम प्रश्न को देखें, तो हम पाएंगे कि 0 से n-1 तक निश्चित रूप से एक पॉइंट मौजूद होगा जहां उस पॉइंट के बाईं ओर के सभी एलिमेंट्स में सभी 0s होने चाहिए और दाईं ओर सभी 1s होने चाहिए
• वे इंडेक्स जो इस नियम का पालन नहीं करते उन्हें हटाना होगा। विचार बाएं से दाएं सभी 0s को गिनना है।

उदाहरण

#include 
using namespace std;

int getMinToggles(int *arr, int n) {
    int zeroCnt[n + 1] = {0};
    for (int i = 1; i <= n; ++i) {
        if (arr[i - 1] == 0) {
            zeroCnt[i] = zeroCnt[i - 1] + 1;
        } else {
            zeroCnt[i] = zeroCnt[i - 1];
        }
    }
    int result = n;
    for (int i = 1; i <= n; ++i) {
        result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
    }
    return result;
}

int main() {
    int arr[] = {1, 0, 0, 1, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
    return 0;
}

जब आप उपरोक्त प्रोग्राम को कंपाइल और 실행 करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -

आउटपुट

Minimum toggles = 2