C++ का उपयोग करते हुए बाइनरी स्ट्रिंग S के योग के लिए आवश्यक न्यूनतम संक्रियाएँ।

समस्या कथन

एक बाइनरी स्ट्रिंग str को देखते हुए। स्ट्र द्वारा दर्शाई गई संख्या बनाने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात कीजिए। केवल निम्नलिखित ऑपरेशन किए जा सकते हैं -

• 2 जोड़ें ^x
• 2 घटाएं ^x

यदि बाइनरी स्ट्रिंग "1000" है तो हमें केवल 1 ऑपरेशन करना होगा यानी 2 जोड़ें ³

यदि बाइनरी स्ट्रिंग "101" है तो हमें 2 ऑपरेशन करने होंगे यानी 2 जोड़ें ² + 2 ⁰

उदाहरण

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int getMinOperations(string s){
   reverse(s.begin(), s.end());
   int n = s.length();
   int result[n + 1][2];
   if (s[0] == '0') {
      result[0][0] = 0;
   } else {
      result[0][0] = 1;
   }
   result[0][1] = 1;
   for (int i = 1; i < n; ++i) {
      if (s[i] == '0') {
         result[i][0] = result[i - 1][0];
         result[i][1] = 1 + min(result[i - 1][1],
         result[i - 1][0]);
      } else {
         result[i][1] = result[i - 1][1];
         result[i][0] = 1 + min(result[i - 1][0],
         result[i - 1][1]);
      }
   }
   return result[n - 1][0];
}
int main(){
   string str = "101";
   cout << "Minimum required operations = " << getMinOperations(str) << endl;
   return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -

Minimum required operations = 2