समस्या कथन
केवल 0 और 1 वाले n पूर्णांकों की एक सरणी को देखते हुए। न्यूनतम टॉगल खोजें (0 से 1 पर स्विच करें या इसके विपरीत) आवश्यक है कि सरणी विभाजित हो जाए, यानी, इसमें पहले 0s फिर 1s हैं।
उदाहरण
अगर arr[] ={1, 0, 0, 1, 1, 1, 0} तो 2 टॉगल की आवश्यकता है यानी पहले एक और अंतिम शून्य को टॉगल करें।
एल्गोरिदम
- यदि हम प्रश्न का अवलोकन करें, तो हम पाएंगे कि निश्चित रूप से 0 से n-1 तक एक बिंदु मौजूद होगा जहां उस बिंदु पर छोड़े गए सभी तत्वों में सभी 0 होने चाहिए और बिंदु के अधिकार में सभी 1 होने चाहिए
- जो सूचकांक इस कानून का पालन नहीं करते हैं उन्हें हटाना होगा। विचार सभी 0 को बाएं से दाएं गिनने का है।
उदाहरण
#include <bits/stdc++.h>
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