C++ में किसी सरणी में सभी मान सेट करने के लिए न्यूनतम दाएं फ़्लिप की गणना करें

हमें 0s और 1s की एक सरणी दी गई है जो क्रम में एक ही तार से जुड़े बल्बों की स्थिति का प्रतिनिधित्व करते हैं। 0 दर्शाता है कि बल्ब बंद है और 1 यह दर्शाता है कि बल्ब चालू है। N बल्बों के ऐसे क्रम के लिए, यदि बल्ब का स्विच दबाया जाता है, तो दाईं ओर के सभी बल्ब, (i+1 th से n तक) अपने पिछले घूरने को, ON से OFF या OFF से ON में बदल देते हैं।

सभी बल्बों की दी गई स्थिति के लिए, उन सभी को चालू करने के लिए दबाए जाने वाले न्यूनतम स्विच को खोजने का लक्ष्य है। [उसी स्विच को कितनी भी बार दबाया जा सकता है]। यह सभी को 1 के रूप में सेट करने के लिए एक सरणी में सही अनुक्रमणिका मानों की स्थिति को फ़्लिप करने जैसा ही है।

इनपुट

Bulbs[]= { 1,0,1,0 }

आउटपुट

Minimum right flips: 3

स्पष्टीकरण

मूल स्थिति 1010

Press switch 2:- 1:101 flip count=1
Press switch 3:- 11:10 flip count=2
Press switch 4:- 111:1 flip count=3

इनपुट

Bulbs[]= { 1,0,0,0 }

आउटपुट

Minimum right flips: 1

स्पष्टीकरण

Original state 1000
Press switch 2:- 1:111 flip count=1

दाईं ओर के सभी बल्ब चालू हैं।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• पूर्णांक एन संख्या के बल्बों की स्थिति को संग्रहीत करता है।

• फ़ंक्शन minFlips(int arr[],int n) इनपुट के रूप में एक सरणी और उसकी लंबाई n लेता है और सरणी के मान सेट करने के लिए सही फ़्लिप की न्यूनतम संख्या देता है (सभी बल्बों को चालू करें)

• वेरिएबल काउंट का इस्तेमाल फ्लिप की संख्या को स्टोर करने के लिए किया जाता है, शुरुआत में 0.

• ऐरे स्विच [] का उपयोग i वें बल्ब से संबंधित सभी स्विच की प्रारंभिक स्थिति को संग्रहीत करने के लिए किया जाता है। सभी 0 हैं ( स्विच [] ={0}।)

• i=0 से n तक हम निम्नलिखित कार्य करते हैं -

  • यदि बल्ब चालू है और स्विच बंद है, तो कुछ न करें (i वृद्धि करें)

  • यदि बल्ब बंद है और स्विच चालू है, तो कुछ भी न करें (i वृद्धि करें) क्योंकि स्विच ऑफ करने से बल्ब की स्थिति पर कोई प्रभाव नहीं पड़ेगा

  • यदि बल्ब बंद है और स्विच बंद है, तो गिनती बढ़ाएं और सभी बल्बों की स्थिति को दाईं ओर मोड़ें। (जबकि लूप)

• लूप के अंत के बाद फ्लिप के रूप में 'गिनती' में मौजूद परिणाम लौटाएं।

• वापसी की संख्या।

उदाहरण

// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int minFlips(int arr[], int n){
   int count = 0;
   int swich[n] = {0}; //Initially we don't flip the states, so flip is false
   for(int i=0;i<n;i++){
      if(arr[i]==1 && swich[i]==0)
         i++;
      if(arr[i]==0 && swich[i]==1)
         i++;
      if(arr[i]==0 && swich[i]==0){
         count++;
         int j=i;
      while(j<n){
         if(arr[j]==0)
            arr[j++]=1;
         else
            arr[j++]=0;
         }
      }
   }
   return count;
}
int main(){
   int Arr[] = {0,1,0,1};
   int N = 4;
   cout <<”Minimum right flips to set all values in an array:"<<
   minFlips(Arr, N);
   return 0;
}

आउटपुट

Minimum right flips to set all values in an array: 4