C++でn回反復後のバイナリ文字列におけるi番目の文字を求める方法

バイナリ文字列 bin があるとします。この文字列に対して n 回の反復処理を適用します。各反復では、0 は「01」に、1 は「10」に変換されます。そして、n 回目の反復後の文字列における i 番目の文字を求めるのがこの問題です。

例えば、バイナリ文字列が「101」で、n = 2、i = 3 の場合を考えてみましょう。1 回目の反復後は「100110」になり、2 回目の反復後は「100101101001」になります。したがって、i 番目のインデックスに格納されている文字は「1」です。

解決の手順

この問題を解くには、以下の手順に従います。

• n 回ループを実行し、各反復内で文字列に対してさらに内側のループを実行する。
  • バイナリ文字列の各文字を変換し、「0」であれば「01」を、「1」であれば「10」を別の一時文字列に格納する。
  • 内側のループが完了したら、一時文字列をバイナリ文字列に代入する。
• 最後に i 番目の文字を返す。

実装例

#include <iostream>
using namespace std;
char getCharacter(string bin_str, int n, int i) {
    string temp = "";
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < bin_str.length(); y++) {
            if (bin_str[y] == '1')
                temp += "10";
            else
                temp += "01";
        }
        bin_str = temp;
        temp = "";
    }
    return bin_str[i];
}
int main() {
    int n = 2;
    string bin = "101";
    cout << 3 << "rd character is: " << getCharacter(bin, n, 3) << endl;
    cout << 9 << "th character is: " << getCharacter(bin, n, 9);
}

出力

3rd character is: 1
9th character is: 0

計算量に関する注意

各反復で文字列の長さは2倍になるため、n 回の反復後の文字列の長さは初期文字列の 2ⁿ 倍に達します。このアプローチの時間計算量は O(2ⁿ × |S|)(|S| は初期文字列の長さ)となるため、n が大きくなるとメモリと時間の両面で非現実的になります。実用上は、n が比較的小さい場合にこの手法を用いるのが適切です。