Pythonで特定の操作を繰り返して全要素を等しくする最小手順を求めるプログラム

数値のリスト nums が与えられ、すべての値を等しくすることを考えます。ここで「リストから1つの要素を選び、それ以外のすべての値を1ずつ増やす」という操作が許されているとします。このとき、すべての要素の値を等しくするために必要な最小の操作回数を求めます。

たとえば、入力が [2, 4, 5] の場合、出力は 5 になります。

解法のポイント

「選んだ要素以外を1ずつ増やす」という操作は、相対的な差に注目すると「選んだ1つの要素だけを1減らす」操作と同じ効果があります。そこで、各要素をリストの最小値まで揃えることを考えると、各要素 num に必要な操作回数は num - min_val となり、その総和が答えになります。

アルゴリズムの手順

• min_val ← リスト内の最小値
• s ← 0(操作回数の合計)
• リスト内の各 num に対して、s に (num - min_val) を加算
• s を返す

この方法なら計算量は O(n) と非常に効率的で、大きなリストでも高速に処理できます。

実装例(Python)

class Solution:
   def solve(self, nums):
      min_val = min(nums)
      s = 0
      for num in nums:
         s += num - min_val
      return s

ob = Solution()
nums = [2, 4, 5]
print(ob.solve(nums))

入力

[2, 4, 5]

出力

5

検算してみると、(2−2) + (4−2) + (5−2) = 0 + 2 + 3 = 5 となり、確かに5回の操作ですべての要素を等しくできることが確認できます。