C++を使用してバイナリ文字列Sに合計するために必要な操作の最小数。

問題の説明

与えられたバイナリ文字列str。 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