हमें 0 और 1 की एक सरणी दी गई है जो क्रम में जुड़े बल्बों की स्थिति को दर्शाती है। 0 दर्शाता है कि बल्ब बंद है और 1 दर्शाता है कि बल्ब चालू है। ऐसे N बल्बों के अनुक्रम के लिए, यदि बल्ब का स्विच दबाया जाता है तो दाईं ओर के सभी बल्ब (i+1वें से n तक) अपनी पिछली स्थिति बदलते हैं, चालू से बंद या बंद से चालू।
दिए गए सभी बल्बों की स्थिति के लिए, लक्ष्य उन सभी को चालू करने के लिए दबाए जाने वाले न्यूनतम स्विच ढूंढना है। [ वही स्विच किसी भी संख्या में दबाया जा सकता है ]। यह सरणी में दाएं इंडेक्स मानों की स्थिति को फ्लिप करके उन सभी को 1 के रूप में सेट करने के समान है।
इनपुट
Bulbs[]= { 1,0,1,0 } आउटपुट
न्यूनतम राइट फ्लिप: 3
व्याख्या: मूल स्थिति 1010
स्विच 2 दबाएं:- 1:101 फ्लिप गणना=1 स्विच 3 दबाएं:- 11:10 फ्लिप गणना=2 स्विच 4 दबाएं:- 111:1 फ्लिप गणना=3
इनपुट
Bulbs[]= { 1,0,0,0 } आउटपुट
न्यूनतम राइट फ्लिप: 1
व्याख्या: मूल स्थिति 1000 स्विच 2 दबाएं:- 1:111 फ्लिप गणना=1
दाईं ओर के सभी बल्ब चालू हो गए।
प्रयुक्त दृष्टिकोण
- पूर्णांक N बल्बों की स्थिति संग्रहीत करता है।
- फ़ंक्शन minFlips(int arr[],int n) एक सरणी और इसकी लंबाई n को इनपुट के रूप में लेता है और सरणी के मान सेट करने के लिए न्यूनतम राइट फ्लिप की संख्या लौटाता है (सभी बंद बल्बों को चालू करें)।
- चर count का उपयोग फ्लिप की संख्या संग्रहीत करने के लिए किया जाता है, प्रारंभ में 0।
- सरणी switch[] का उपयोग iवें बल्ब से संबंधित सभी स्विच की प्रारंभिक स्थिति संग्रहीत करने के लिए किया जाता है। सभी 0 हैं (switch[]={0}।)
- i=0 से n तक शुरू करके हम निम्नलिखित करते हैं:
- यदि बल्ब चालू है और स्विच बंद है, तो कुछ न करें (i बढ़ाएं)
- यदि बल्ब बंद है और स्विच चालू है, तो कुछ न करें (i बढ़ाएं) क्योंकि स्विच बंद करने से बल्ब की स्थिति पर कोई असर नहीं पड़ेगा
- यदि बल्ब बंद है और स्विच बंद है, तो count बढ़ाएं और दाईं ओर के सभी बल्बों की स्थिति बदलें। (while लूप)
- for लूप के अंत में 'count' में मौजूद परिणाम को फ्लिप के रूप में लौटाएं।
- count लौटाएं।
उदाहरण कोड
// C++ प्रोग्राम आइटम को सॉर्ट क्रम में व्यवस्थित करने के लिए न्यूनतम मूव-टू-फ्रंट चाल ढूंढने के लिए #include <bits/stdc++.h> using namespace std; // सरणी को बढ़ते क्रम में व्यवस्थित करने के लिए न्यूनतम चालों की गणना करें int minFlips(int arr[], int n){ int count = 0; int swich[n] = {0}; //प्रारंभ में हम स्थितियों को फ्लिप नहीं करते, इसलिए फ्लिप गलत है for(int i=0;i आउटपुट
सरणी में सभी मान सेट करने के लिए न्यूनतम राइट फ्लिप: 4