C++でxで割り切れるバイナリ配列の接頭辞（プレフィックス）を数える方法

このチュートリアルでは、バイナリ配列の接頭辞（プレフィックス）のうち、指定した値 x で割り切れるものの個数を求めるプログラムについて解説します。

具体的には、バイナリ配列と整数値 x が与えられ、先頭から各要素までを見たときに構成される2進数（接頭辞）が x で割り切れる箇所がいくつあるかを数えるのが目的です。

アルゴリズムの考え方

配列を先頭から順に走査しながら、それまでの要素で表される2進数の値を更新していきます。新しい桁が追加されると、これまでの値は「前の値 × 2 ＋ 現在のビット」で表されます。この値が x で割り切れるたびにカウントを1つ増やし、最終的なカウントを結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
// 接頭辞がxで割り切れる要素の個数を数える
int count_divx(int arr[], int n, int x){
    int number = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        // 2進数として値を更新
        number = number * 2 + arr[i];
        // xで割り切れたらカウントを増やす
        if ((number % x == 0))
            count += 1;
    }
    return count;
}
int main(){
    int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    cout << count_divx(arr, n, x);
    return 0;
}

出力結果

3

コードの解説

この例では、配列 {1, 0, 1, 0, 1, 1, 0} と x = 2 を使用しています。先頭からの接頭辞は順に「1」「10」「101」「1010」「10101」「101011」「1010110」という2進数になります。

これらを10進数に直すと 1, 2, 5, 10, 21, 43, 86 となり、このうち 2 の倍数（x = 2 で割り切れる値）は「2」「10」「86」の3つです。そのため、出力は 3 となります。

計算量

配列を一度だけ走査するため、時間計算量は O(n)、必要な追加メモリは定数 O(1) と非常に効率的なアルゴリズムです。ただし、接頭辞の値が大きくなるとオーバーフローする可能性があるため、大きな入力に対しては剰余を取りながら計算するなどの工夫が必要になる場合があります。