इस समस्या में, हमें एक बाइनरी सरणी bin[] दी गई है जिसमें n बाइनरी मान (0 और 1) होते हैं। हमारा कार्य सरणी को सुंदर बनाने के लिए आवश्यक न्यूनतम संचालन ज्ञात करना है।
सुंदर सरणी एक विशेष प्रकार की बाइनरी सरणी है जिसमें 0 और 1 का वैकल्पिक पैटर्न होता है।
समस्या विवरण - हमें उन संचालनों की संख्या ज्ञात करनी है जो सरणी को सुंदर बनाने के लिए आवश्यक हैं। एक संचालन में ये चरण होते हैं:
चरण 1 - सरणी को दो हिस्सों में काटें।
चरण 2 - दो हिस्सों में से किसी एक को उलट दें।
चरण 3 - दोनों हिस्सों को फिर से जोड़ दें।
हम उन संचालनों की गणना करेंगे जो यह सुनिश्चित करने के लिए आवश्यक हैं कि सरणी एक सुंदर सरणी बन जाए।
आइए एक उदाहरण से समझते हैं:
इनपुट
bin[] = {1, 0, 1, 0, 0, 1}आउटपुट
1
व्याख्या
हम सरणी को काटेंगे, उप-सरणी bin[4, 5] बनाएँगे, उसे उलट देंगे और फिर से जोड़ देंगे।
समाधान दृष्टिकोण
समस्या का समाधान न्यूनतम स्विच संचालन खोजने पर आधारित है जो लगातार शून्यों की संख्या के बराबर होता है। आधार मामले हैं:
- यदि सरणी का आकार 1 है, तो यह पहले से ही सुंदर सरणी है।
- यदि सरणी का आकार विषम संख्या है तो यह कभी भी सुंदर सरणी नहीं बन सकती।
सभी सम लंबाई के लिए, हम लगातार शून्यों या ones की कुल संख्या की जाँच करेंगे जो किए जाने वाले संचालनों की संख्या होगी।
एल्गोरिदम
- प्रारंभ करें - zeroCount, oneCount, consZero = 0
- चरण 1 - यदि (n = 1), 0 लौटाएँ
- चरण 2 - यदि (n%2 != 0), -1 लौटाएँ।
- चरण 3 - i = 0 से n-1 तक लूप चलाएँ।
- चरण 3.1 - यदि bin[i] == bin[i+1] == 0, तो consZero++।
- चरण 4 - यदि bin[n-1] == bin[0] == 0, तो consZero++।
- चरण 5 - consZero लौटाएँ।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
उदाहरण
#include <iostream> using namespace std; int minOperations(int bin[], int n) { if(n == 1) return 0; if(n%2 != 0) return -1; int consZero = 0; for (int i = 0; i < n; ++i) { if (i + 1 < n) { if (bin[i] == 0 && bin[i + 1] == 0) consZero++; } } if (bin[0] == bin[n - 1] && bin[0] == 0) consZero++; return consZero; } int main() { int bin[] = { 1, 0, 1, 0, 0, 1}; int n = sizeof(bin) / sizeof(bin[0]); cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n); return 0; }आउटपुट
The minimum operations needed to make an Array beautiful is 1
