Pythonで目標の合計に到達するために追加すべき最小要素数を求めるプログラム

nums という整数配列と、limit・goal という2つの値が与えられているとします。この配列は特殊な条件を満たしており、すべてのインデックス i(0 から配列サイズ − 1 まで)に対して |nums[i]| ≤ limit が成立しています。ここでの課題は、配列全体の合計が goal と一致するようにするために、追加で挿入すべき要素の最小個数を求めることです。なお、新たに追加する要素についても、その絶対値が limit を超えてはいけません。

例として、nums = [2,-2,2]、limit = 3、goal = -4 が入力された場合を考えてみましょう。この場合の出力は 2 になります。-3 を2つ追加すれば配列は [2,-2,2,-3,-3] となり、合計がちょうど -4(goal)に一致するからです。

解決アプローチ

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

• s := 配列 nums 内の全要素の合計

• ab := |goal − s|(現在の合計と目標との差の絶対値)

• (ab ÷ limit) の切り上げ値を返す

このアプローチが正しく機能する理由は次のとおりです。1つの追加要素によって合計を変化させられる量は最大でも limit であるため、差 ab を埋めるには少なくとも ⌈ab ÷ limit⌉ 個の要素がどうしても必要になります。逆に言えば、±limit を組み合わせて調整しながら ⌈ab ÷ limit⌉ 個の要素を追加すれば、必ず差をぴったり埋められるため、これが最小個数となります。計算量は配列の合計を求める O(n) だけで済み、非常に効率的です。

実装例

それでは、以下の Python 実装を見て理解を深めましょう。

from math import ceil

def solve(nums, limit, goal):
   s = sum(nums)
   ab = abs(goal - s)
   return ceil(ab / limit)

nums = [2,-2,2]
limit = 3
goal = -4
print(solve(nums, limit, goal))

入力

[2,-2,2], 3, -4

出力

2

なお、Python 3 では math.ceil 関数が整数型(int)を返すため、出力は 2 と表示されます。切り上げ処理によって、差が limit で割り切れない場合にも必要な要素数が正確に算出される点がポイントです。