Pythonで奇数桁と偶数桁の合計の差を判定するプログラム

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

問題文

整数が1つ与えられたとき、奇数桁の合計と偶数桁の合計の差が0であるかどうかを判定する必要があります。

素朴なアプローチ（ブルートフォース）

最も単純な方法は、数値を構成するすべての偶数桁と奇数桁の合計をそれぞれ計算し、その差を求めることです。しかし、この方法では各桁を順番に処理するため、桁数に比例した計算時間が必要になります。

効率的なアプローチ：11の倍数判定を活用

計算時間を削減するために、「暗算の数学」でよく知られている性質を利用します。それは「ある整数の奇数桁の合計と偶数桁の合計の差が0になるのは、その数が11で割り切れる場合に限る」というものです。

したがって、以下の実装では、数値が11で割り切れるかどうかを確認するだけで判定を行います。

これにより、計算量は O(n) から、剰余演算と比較に必要な定数時間 O(1) へと大幅に削減されます。

実装例

def isDiff(n):
    return (n % 11 == 0)

# main
n = 785643
if (isDiff(n)):
    print("Yes")
else:
    print("No")

出力結果

No

この例では、785643は11で割り切れないため「No」が出力されます。すべての変数と関数は、下図のようにグローバルスコープで宣言されています。

まとめ

この記事では、整数の奇数桁と偶数桁の合計の差を計算・判定するアプローチについて学びました。各桁を実際に足し合わせる代わりに、11の倍数判定という数学的な性質を利用することで、非常に効率的に問題を解けることを確認しました。同様の性質は、競技プログラミングやアルゴリズムの最適化の場面でも応用できる有用なテクニックです。