Pythonで合計をkで割り切れるようにするために削除できる最小の部分リストの長さを求めるプログラム

問題の概要

正の整数のみを含むリスト nums と、正の整数 k が与えられます。残りの要素の合計が k で割り切れるようになるように、nums から削除できる最短の部分リスト(連続する要素列)の長さを求めてください。部分リストは空でも構いませんが、リスト全体を削除することはできません。条件を満たす削除方法が存在しない場合は -1 を返します。

具体例

例として、nums = [5, 8, 6, 3]、k = 8 のケースを考えてみましょう。現在の要素の合計は 5 + 8 + 6 + 3 = 22 です。ここで長さ 1 の部分リスト [6] を取り除くと、残りの合計は 16 となり、8 で割り切れます。したがって、この場合の出力は 1 となります。

解法の考え方

この問題は、累積和(プレフィックスサム)とハッシュマップ(辞書)を組み合わせることで、時間計算量 O(n) で効率的に解くことができます。

ポイントは、「残りの合計が k で割り切れる」という条件を、「削除する部分リストの合計が、全体の合計を k で割った余りと一致する」という条件に読み替えることです。具体的な手順は以下の通りです。

• rem := リスト全体の合計を k で割った余り、すなわち (sum(nums) + k) % k
• rem が 0 の場合 → 削除は不要なので 0 を返す
• n := リスト nums の長さ
• presum := 累積和を記録する変数(初期値 0)
• mp := 各余りに対して最新のインデックスを記録する辞書(キー 0 には初期値 -1 を設定)
• res := 答えの候補(初期値は n)
• i を 0 から n-1 まで繰り返す:
  • presum に nums[i] を加算する
  • m := (presum + k) % k を計算し、mp[m] = i として記録する
  • (m - rem + k) % k が mp に存在する場合、res と i - mp[(m - rem + k) % k] の小さい方で res を更新する
• 最後に、res が n と等しくなければ res を、等しければ -1 を返す

各余りの値について「最も右側(最新)のインデックス」だけを辞書に保持することで、各位置 i に対して「そこで終わる最短の削除候補」を常に評価できます。これにより、すべての区間を調べる O(n²) の素朴な解法と比べて、大幅に高速な処理が可能になります。

実装例(Python)

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

def solve(nums, k):
    rem = (sum(nums) + k) % k
    if rem == 0:
        return 0
    n, presum = len(nums), 0
    mp = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        m = (presum + k) % k
        mp[m] = i
        if (m - rem + k) % k in mp:
            res = min(res, i - mp[(m - rem + k) % k])
    return res if res != n else -1

nums = [5,8,6,3]
k = 8
print(solve(nums, k))

入力

[5,8,6,3], 8

出力

1

まとめ

本記事では、リストの合計を k で割り切れるようにするために削除すべき最短の部分リストの長さを求める Python プログラムを紹介しました。累積和と余りの管理を辞書で行うことで、線形時間 O(n) での解法が実現できます。この「余り × 累積和 × ハッシュマップ」のテクニックは、区間和に関する剰余問題全般に応用できる便利な手法なので、ぜひ覚えておきましょう。