समस्या कथन
एक बाइनरी स्ट्रिंग str दी गई है। str द्वारा दर्शाई गई संख्या बनाने के लिए किए जाने वाले न्यूनतम ऑपरेशन की संख्या ढूंढें। केवल निम्न ऑपरेशन किए जा सकते हैं:
- 2ˣ जोड़ें
- 2ˣ घटाएं
यदि बाइनरी स्ट्रिंग "1000" है, तो केवल 1 ऑपरेशन करना होगा: 2³ जोड़ें।
यदि बाइनरी स्ट्रिंग "101" है, तो 2 ऑपरेशन करने होंगे: 2² + 2⁰ जोड़ें।
C++ उदाहरण
#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
