मान लीजिए '0' और '1' की एक स्ट्रिंग दी गई है। वह स्ट्रिंग मोनोटोनिक बढ़ रही होगी यदि इसमें कुछ संख्या में '0' (संभवतः 0) शामिल हैं, इसके बाद कुछ '1' (संभवतः 0.) भी हैं। हमारे पास '0' और '1' की एक स्ट्रिंग S है, और हम किसी भी '0' को '1' या '1' को '0' में फ़्लिप कर सकते हैं। S मोनोटोन को बढ़ाने के लिए फ़्लिप की न्यूनतम संख्या ज्ञात कीजिए। तो अगर इनपुट "010110" जैसा है, तो आउटपुट 2 होगा। फ्लिप करके हम "011111" या "000111" प्राप्त कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n:=S का आकार, फ्लिपकाउंट सेट करें:=0, वनकाउंट:=0
-
मैं के लिए 0 से n - 1 की सीमा में
-
अगर S[i] 0 है, तो
-
अगर वनकाउंट =0 है, तो अगले पुनरावृत्ति पर जाएं
-
फ्लिपकाउंट को 1 से बढ़ाएं
-
-
अन्यथा वनकाउंट को 1 से बढ़ाएं
-
अगर वनकाउंट <फ्लिपकाउंट, फिर फ्लिपकाउंट सेट करें:=वनकाउंट
-
-
वापसी फ्लिपकाउंट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFlipsMonoIncr(string S) {
int n = S.size();
int flipCount = 0;
int oneCount = 0;
for(int i = 0; i < n; i++){
if(S[i] == '0'){
if(oneCount == 0) continue;
flipCount++;
} else oneCount++;
if(oneCount < flipCount) flipCount = oneCount;
}
return flipCount;
}
};
main(){
Solution ob;
cout << (ob.minFlipsMonoIncr("010110"));
} इनपुट
"010110"
आउटपुट
2