C++ में सरणी पर ऑपरेशन करके सभी तत्वों को 0 बनाने के लिए न्यूनतम ऑपरेशन

समस्या कथन

आकार N की एक सरणी दी गई है और प्रत्येक तत्व या तो 1 या 0 है। सभी तत्वों को शून्य में बदलने के लिए किए जाने वाले न्यूनतम ऑपरेशन की गणना करें। कोई निम्न ऑपरेशन कर सकता है:

यदि कोई तत्व 1 है, तो आप उसका मान 0 के बराबर बदल सकते हैं, तब:

• यदि अगला लगातार तत्व 1 है, तो यह स्वचालित रूप से 0 में बदल जाएगा
• यदि अगला लगातार तत्व पहले से 0 है, तो कुछ नहीं होगा

यदि arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}, तो सभी तत्वों को शून्य बनाने के लिए 4 ऑपरेशन आवश्यक हैं।

एल्गोरिदम

1. यदि वर्तमान तत्व 1 है तो काउंट बढ़ाएं और अगले 0 को खोजें क्योंकि सभी लगातार 1 स्वचालित रूप से 0 में बदल जाएंगे।
2. अंतिम काउंट लौटाएं

C++ उदाहरण

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int performMinOperation(int *arr, int n) {
    int i, cnt = 0;
    for (i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            int j;
            for (j = i + 1; j < n; ++j) {
                if (arr[j] == 0) break;
            }
            i = j - 1;
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
    cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
    return 0;
}

आउटपुट

Minimum required operations = 4