下の桁から繰り上がりを運び、桁の並びに 1 を足す

数学と行列問題 144

10 進の数を上の桁から並べた桁の並びに 1 を足し、結果も桁の並びで返します。数に直さず、いちばん下の桁から繰り上がりを運び、全部 9 のときだけ頭に 1 を足す練習です。

海外で定番の問題リスト 4 本には入っていません

問題

通し番号を振る仕組みで、番号が 10 進の桁の並び digits で渡されます。並びの先頭がいちばん上の桁です。この番号に 1 を足した番号を、同じく上の桁からの桁の並びで返す関数を書いてください。

digits の各値は 0 以上 9 以下です
番号が 0 そのもの ([0]) のときを除き、先頭は 0 ではありません
digits の長さは 1 以上 100 以下です。数の型に直すと入りきらない長さもあるので、桁の並びのまま足してください

入力と出力の例

例 1

いちばん下の桁が 9 でなければ、そこに 1 を足すだけです。

digits = [2, 0, 4, 7]

[2, 0, 4, 8]

例 2

下の 2 桁が 9 なので、0 になって上へ繰り上がります。

digits = [3, 9, 9]

[4, 0, 0]

例 3

全部の桁が 9 だと、桁が 1 つ増えます。

digits = [9, 9, 9]

[1, 0, 0, 0]

面接での聞かれ方

面接では、手慣らしの 1 問として出されることが多い問題です。

「配列で表した整数に 1 を足してください」
数に直して足し、並びに戻す書き方を見せると、「100 桁あったらどうしますか？」と聞かれます
「全部 9 のときはどうなりますか？」と、端の場合を聞かれます

筆算の繰り上がりを、そのままコードにできるかが見られています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

数に直して 1 を足し、桁に戻す書き方は、32 ビットや 64 ビットの整数に入りきらない長さで壊れます。並びのまま、筆算と同じく下の桁から足します。

段 2

いちばん下の桁から見ていきます。9 でなければ 1 を足して、そこで終わりです。それより上の桁は変わりません。9 なら 0 にして、1 つ上の桁へ繰り上がりを運びます。

段 3

全部の桁が 9 だと、最後まで繰り上がりが残ります。このときの答えは、頭が 1 で残りが全部 0 の、1 つ長い並びです。

解答

Python

def plus_one(digits):
    out = list(digits)
    for i in range(
        len(out) - 1, -1, -1
    ):
        if out[i] < 9:
            out[i] += 1
            return out
        out[i] = 0
    return [1] + out

JavaScript

function plusOne(digits) {
  const out = [...digits];
  for (
    let i = out.length - 1;
    i >= 0;
    i--
  ) {
    if (out[i] < 9) {
      out[i] += 1;
      return out;
    }
    out[i] = 0;
  }
  return [1, ...out];
}

Go

func plusOne(digits []int) []int {
	out := make([]int, len(digits))
	copy(out, digits)
	for i := len(out) - 1; i >= 0; i-- {
		if out[i] < 9 {
			out[i]++
			return out
		}
		out[i] = 0
	}
	return append([]int{1}, out...)
}

どの言語も、受け取った並びを写してから書き換えています。呼び出し元の digits は変わりません。

計算量

時間は、桁の数を n として O(n) です。いちばん悪いのは全部が 9 のときで、全部の桁を 1 回ずつ見ます
使う記憶は、答えの並びの分の O(n) です
下の桁が 9 でなければ 1 桁見ただけで終わるので、ふつうはすぐに返ります

よくある間違い

数に直して足す。例 3 のような短い並びでは動きますが、20 桁を超えると 64 ビットの整数に入りきらず、JavaScript の数では下の桁が狂います
繰り上がりの後に止め忘れる。 9 でない桁に 1 を足したら、すぐに返します。続けて上の桁も見ると、ほかの桁まで書き換えてしまいます
全部 9 の場合を忘れる。例 3 で、最後まで繰り上がったのに [0, 0, 0] を返してしまいます。頭に 1 を足します
上の桁から足し始める。繰り上がりは下から上へ運ぶので、並びの末尾から見ます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def plus_one(digits: list[int]) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(plus_one([2, 0, 4, 7]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します