C++ में शून्यों को फ्लिप करके अधिकतम लगातार 1s प्राप्त करना

परिचय

इस ट्यूटोरियल में हम उन शून्यों (zeroes) की संख्या ढूंढेंगे जिन्हें फ्लिप करके सरणी में अधिकतम लगातार 1s प्राप्त किए जा सकते हैं।

हम इस समस्या को हल करने के लिए स्लाइडिंग विंडो (sliding window) दृष्टिकोण का उपयोग करेंगे।

समस्या समाधान के चरण

सरणी और फ्लिप किए जा सकने वाले अधिकतम शून्यों को इनिशियलाइज़ करें।
विंडो प्रारंभ, अंत इंडेक्स और लंबाई इनिशियलाइज़ करें।
लगातार 1s की अधिकतम सब-सरणी की लंबाई और प्रारंभिक इंडेक्स स्टोर करें।
सरणी पर पुनरावृत्ति करें जब तक अंत इंडेक्स सरणी की लंबाई पार न कर जाए।
यदि शून्यों की संख्या अधिकतम शून्यों से कम या बराबर है तो अंत इंडेक्स बढ़ाएं और यदि वर्तमान मान शून्य है तो शून्यों की संख्या बढ़ाएं।
यदि शून्यों की संख्या अधिकतम से अधिक है तो प्रारंभ इंडेक्स बढ़ाएं और यदि वर्तमान मान शून्य है तो शून्यों की संख्या घटाएं।
यदि वर्तमान विंडो लंबाई पिछली से अधिक है तो अधिकतम विंडो अपडेट करें।
सरणी पर पुनरावृत्ति करें और विंडो प्रारंभ इंडेक्स का उपयोग करके शून्य इंडेक्स प्रिंट करें।

उदाहरण कोड

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

void zeroesIndexes(int arr[], int maxZeroes, int n) {
    int start = 0, end = 0;
    int zeroesCount = 0;
    int bestWindowCount = 0, bestWindowStartIndex = 0;
    while (end < n) {
        if (zeroesCount <= maxZeroes) {
            if (arr[end] == 0) {
                zeroesCount++;
            }
            end++;
        }
        if (zeroesCount > maxZeroes) {
            if (arr[start] == 0) {
                zeroesCount--;
            }
            start++;
        }
        if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
            bestWindowCount = end - start;
            bestWindowStartIndex = start;
        }
    }
    cout << "The indexes are ";
    for (int i = 0; i < bestWindowCount; ++i) {
        if(arr[bestWindowStartIndex + i] == 0)
            cout << bestWindowStartIndex + i << " ";
    }
}

int main() {
    int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
    int maxZeroes = 2;
    zeroesIndexes(arr, maxZeroes, 10);
    return 0;
}

आउटपुट

The indexes are 5 7

व्याख्या

सरणी: [1, 0, 0, 1, 1, 0, 1, 0, 1, 1], maxZeroes = 2

इंडेक्स 5 और 7 पर शून्यों को फ्लिप करने से अधिकतम लगातार 1s (इंडेक्स 3 से 9 तक: 1,1,1,1,1,1,1) प्राप्त होते हैं।

निष्कर्ष

स्लाइडिंग विंडो तकनीक इस समस्या को O(n) समय में हल करती है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।