Pythonで5で割り切れる2進数プレフィックスを判定するアルゴリズム

問題の概要

0と1のみで構成された配列Aが与えられます。ここでN[i]とは、「A[0]からA[i]までの部分配列を2進数として解釈した数値」のことです。本記事のゴールは、N[i]が5で割り切れるとき、かつそのときに限りanswer[i]がtrueとなるブール値（真偽値）のリストを求めることです。

例えば、入力が[0,1,1,1,1,1]の場合、出力は[true, false, false, false, true, false]となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• length：配列Aのサイズを取得します。
• ans：長さlengthの配列を作成し、すべてfalseで初期化します。
• number：Aの各要素を連結した文字列を、2進数として整数に変換します。
• iを0からlength-1までループ処理します。
  • numberを5で割った余りが0であれば、ans[length-i-1]をTrueに設定します。
  • numberを1ビット右シフトします（number := number / 2）。
• 最後にansを返します。

このアプローチのポイントは、大きな整数を右シフトしていくことで、末尾のビットを1つずつ取り除いた値、すなわち元の配列の「接頭辞（プレフィックス）」を後ろから順に取得できる点にあります。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def prefixesDivBy5(self, A):
        length = len(A)
        ans = [False] * length
        number = int("".join(map(str, A)), 2)
        for i in range(length):
            if number % 5 == 0:
                ans[length - i - 1] = True
            number = number >> 1
        return ans

ob = Solution()
print(ob.prefixesDivBy5([0,1,1,1,1,1]))

入力

[0,1,1,1,1,1]

出力

[True, False, False, False, True, False]

より効率的な代替手法

上記の実装では、配列全体を一度に大きな整数へ変換しています。配列が非常に長い場合には巨大な整数を扱うことになり、計算コストやメモリ使用量が増大する可能性があります。そこで、左から1ビットずつ処理しながら「5で割った余り」だけを管理する方法も有効です。

class Solution:
    def prefixesDivBy5(self, A):
        ans = []
        num = 0
        for bit in A:
            num = (num * 2 + bit) % 5
            ans.append(num == 0)
        return ans

この方法では各ステップで余りのみを保持するため、配列がどれほど長くなっても時間計算量はO(n)で済み、メモリ使用量も一定に抑えられます。モジュロ演算を活用したこの手法は、競技プログラミングや実務のデータ処理においても非常に有用なテクニックです。