Minimum number of operations required to sum to binary string S using C++.

Problem statement

Given a binary string str. Find the minimum number of operations required to be performed to create the number represented by str. Only following operations can be performed −

• Add 2^x
• Subtract 2^x

If binary string is “1000” then we have to perform only 1 operation i.e. Add 2³

If binary string is “101” then we have to perform 2 operations i.e. Add 2² + 2⁰

Example

#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; }

Output

When you compile and execute above program. It generates following output −

Minimum required operations = 2