C++ में सभी 1s को एक साथ ग्रुप करने के लिए न्यूनतम स्वैप

समस्या कथन

0s और 1s का एक ऐरे दिया गया है। कार्य ऐरे में मौजूद सभी 1s को एक साथ ग्रुप करने के लिए आवश्यक न्यूनतम स्वैप की संख्या ढूंढना है।

उदाहरण

यदि इनपुट ऐरे = {1, 0, 1, 1, 0, 1} तो 1 स्वैप आवश्यक है। यानी पहले 0 को अंतिम 1 से स्वैप करें।

एल्गोरिदम

• ऐरे में कुल 1s की संख्या गिनें
• यदि गिनती x है, तो हमें इस ऐरे की लंबाई x का वह सबएरे ढूंढना होगा जिसमें अधिकतम 1s हों
• न्यूनतम स्वैप की आवश्यकता अधिकतम 1s वाले आकार x के सबएरे में 0s की संख्या होगी

उदाहरण

#include 
using namespace std;

int getMinSwaps(int *arr, int n) {
    int oneCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            ++oneCnt;
        }
    }
    int x = oneCnt;
    int maxOnes = INT_MIN;
    int preCompute[n] = {0};
    if (arr[0] == 1) {
        preCompute[0] = 1;
    }
    for (int i = 1; i < n; ++i) {
        if (arr[i] == 1) {
            preCompute[i] = preCompute[i - 1] + 1;
        } else {
            preCompute[i] = preCompute[i - 1];
        }
    }
    for (int i = x - 1; i < n; ++i) {
        if (i == (x - 1)) {
            oneCnt = preCompute[i];
        } else {
            oneCnt = preCompute[i] - preCompute[i - x];
        }
        if (maxOnes < oneCnt) {
            maxOnes = oneCnt;
        }
    }
    int swapCnt = x - oneCnt;
    return swapCnt;
}

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

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

आउटपुट

Minimum swap count = 1