【Python】配列内のすべての桁を使って3で割り切れる数を作成できるか判定する方法

この記事では、与えられた問題文を解決するための解法とアプローチについて詳しく解説します。

問題文

整数の配列が入力として与えられたとき、これらの数値に含まれるすべての桁を使用して、3で割り切れる整数を作成できるかどうかを判定する必要があります。

ここでは、整数の配列と配列の長さという2つの引数を受け取る関数を作成します。

解法のポイント

この実装は、暗算でよく使われる数学的な性質に基づいています。それは次の通りです。

「ある数の各桁の合計が3で割り切れるならば、その数自体も3で割り切れる」

この性質を利用すると、実際に桁を組み合わせて数値を生成する必要はなく、配列内の各要素について3で割った余りを累積的に計算するだけで判定できます。計算量はO(n)となり、非常に効率的です。

実装例

def isPossibleToMakeDivisible(arr, n):
    remainder = 0
    for i in range(0, n):
        remainder = (remainder + arr[i]) % 3
    return (remainder == 0)

# main()
arr = [33, 40, 90]
n = 3
if (isPossibleToMakeDivisible(arr, n)):
    print("Yes")
else:
    print("No")

出力結果

No

コードの解説

このコードでは、変数 remainder を使って、配列内のすべての要素を順番に加算しながら3で割った余りを更新していきます。最終的に remainder が0であれば、すべての桁を使って3で割り切れる数を作成できることになります。

上記の例では、33 + 40 + 90 = 163 となり、163 を3で割ると余りは1になるため、出力は No となります。

なお、すべての変数と関数は、下図のようにグローバルスコープで宣言されています。

まとめ

この記事では、「3で割り切れる数の各桁の合計もまた3で割り切れる」という数学的な性質を活用し、配列内のすべての桁を使用して3で割り切れる数を作成できるかどうかを効率的に判定する方法を学びました。この手法により、桁の並べ替えを実際に行うことなく、線形時間で問題を解決できます。