सी ++ कोड दिए गए बाइनरी स्ट्रिंग से न्यूनतम सही स्ट्रिंग खोजने के लिए

मान लीजिए कि हमारे पास n बिट्स के साथ एक बाइनरी स्ट्रिंग S है। कोई निरर्थक अग्रणी शून्य नहीं हैं। हम S पर दो अलग-अलग ऑपरेशन कर सकते हैं -

• आसन्न बिट्स के किसी भी जोड़े को स्वैप करें

• सभी "11" को "1" से बदलें

मान लें कि वैल (एस) एस का दशमलव प्रतिनिधित्व है। हमें न्यूनतम सही स्ट्रिंग ढूंढनी है, जहां वैल (ए) <वैल (बी)

इसलिए, यदि इनपुट S ="1001" जैसा है, तो आउटपुट 100 होगा, क्योंकि हम "1001" -> "1010" -> "1100" -> "100" जैसे ऑपरेशन कर सकते हैं।

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n := size of S
res := a blank string
res := res + S[0]
for initialize i := 1, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      res := res concatenate "0"
return res

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
   int n = S.size();
   string res = "";
   res += S[0];
   for (int i = 1; i < n; i++){
      if (S[i] == '0'){
         res += "0";
      }
   }
   return res;
}
int main(){
   string S = "1001";
   cout << solve(S) << endl;
}

इनपुट

"1001"

आउटपुट

100