Pythonでリスト形式の数値に1を加算する方法

問題概要

整数のリスト n が与えられ、これが10進数の数値を表しているとします。各要素 n[i] は 0〜9 の範囲にあります。例えば、n = [2, 4, 9] は数値 249 を表します。このリストと同じ形式で、元の数値に1を加えた結果を返すことが求められます。

例えば、入力が n = [9, 9] の場合、99 + 1 = 100 となるため、出力は [1, 0, 0] になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• リスト n の先頭に 0 を追加します(桁上がりへの備え)
• 最後の要素に1を加えます
• リストの末尾から先頭に向かって処理を行い、10以上の値があれば繰り上げます
  • n[i-1] に n[i] を10で割った商を加算する
  • n[i] を10で割った余りで更新する
• 先頭の要素が0より大きければそのまま返し、そうでなければ先頭を除いたリストを返します

実装例

class Solution:
    def solve(self, n):
        n = [0] + n
        n[-1] += 1
        for i in range(len(n) - 1, 0, -1):
            n[i-1] += n[i] // 10
            n[i] = n[i] % 10
        return n if n[0] > 0 else n[1:]

ob = Solution()
print(ob.solve([9,9]))

入力

[9,9]

出力

[1, 0, 0]

アルゴリズムのポイント

この解法の鍵となるのは、処理の最初に先頭へ 0 を追加しておく点です。これにより、[9, 9, 9] のようにすべての桁が9であるケースでも、桁上がりによって桁数が増える場合に正しく対応できます。

また、リストを一度だけ末尾から走査するため、リストの長さを N とすると計算量は O(N)、追加のメモリも先頭の1要素分のみで済み、非常に効率的なアルゴリズムです。