C++でバイナリ文字列内の偶数となる10進値の部分文字列を数える方法

0と1のみで構成された文字列が与えられます。この文字列は、左から右に読む2進数を表しており、たとえば「001」は1ではなく4を意味します。今回の目的は、10進数として偶数の値を表すすべての部分文字列を見つけることです。

この問題は、各部分文字列の先頭の値を確認するだけで解決できます。先頭が0であればその数は偶数になり、1であれば奇数になります。str[0]='0'で始まるすべての部分文字列は10進数で偶数となるため、countに(length - i)を加算していきます。

具体例を使って理解しましょう。

入力 − str="101"

出力 − バイナリ文字列における偶数の10進値を持つ部分文字列の数 − 2

説明 − 考えられる部分文字列は「10」「11」「01」「0」「1」であり、このうち「01」は2、「0」は0を表すため、偶数は2つです。

入力 − str="111"

出力 − バイナリ文字列における偶数の10進値を持つ部分文字列の数 − 0

説明 − 考えられる部分文字列は「11」「1」であり、偶数となるものは1つもありません。

プログラムで使用するアプローチ

• 0と1のみを含む文字列strを受け取ります。

• strの長さをlen=str.length()として保存します。

• 関数count_even(string str, int length)が文字列とその長さを受け取り、偶数の10進数となる部分文字列の個数を返します。

• FORループを使用して文字列を走査します。

• インデックスi=0からi<lenまで、左から右へ2進数として読み進めます。

• str[i]=='0'である場合、そこから始まるすべての部分文字列は10進数で偶数になります。

• countにlength-iを加算します。

• 結果としてcountを返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int count_even(string str, int length){
    int count = 0;
    for (int i = 0; i < length; i++){
       if (str[i] == '0'){
          count += (length - i);
       }
    }
    return count;
}
int main(){
    string str = "00111";
    int len = str.length();
    cout<<"Count of even decimal value substrings in a binary string are: "<<count_even(str, len) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

Count of even decimal value substrings in a binary string are: 9