Plus One
0以上の整数が、その10進数の各桁を格納した配列digitsとして、最上位桁から順に保存されています。472は[4, 7, 2]です。この数に1を加え、結果の各桁を同じ形式で返してください。この数は最大100桁になることがあり、64ビット整数で扱える桁数を大幅に超えます。
関数
- digitsinteger-array
- 数値の各桁を、最上位桁から順に
- 戻り値integer-array
- 数値の各桁に1を足したもの（最上位桁から順）
制約
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digitsには先頭のゼロはありません。ただし、数値0自体は[0]です。
例
- 入力
- digits = [4, 3, 9]
- 出力
- [4, 4, 0]
- 説明
- 数は439で、439 + 1 = 440です。最後の桁の9は0になり、繰り上がりが3に渡されて、3は4になります。
- 入力
- digits = [9, 9]
- 出力
- [1, 0, 0]
- 説明
- 99 + 1 = 100。2つの9はどちらも0になり、残った繰り上がりが新しい先頭の桁になるため、答えは入力より1桁長くなります。
- 入力
- digits = [0]
- 出力
- [1]
- 説明
- 数字の0は
[0]と書き、0 + 1 = 1です。
提出時に隠しテスト+13件
発展問題
代わりに 1 を引くにはどうすればよいでしょうか。数が 1 以上の場合、どの桁が変化し、[1, 0, 0] のように結果の先頭の桁がなくなるのはどんなときでしょうか。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数値は100桁になることもあり、どの組み込み整数型にも大きすぎます。紙に書いて足し算をするように、各桁で足し算をします。最初に1はどこに行きますか？
9 未満の桁に 1 を足しても繰り上がりは発生しないため、その左側は何も変わりません。9 だけが 0 に変わり、繰り上がりを左へ送ります。
最後の桁から左へ進みます。各9を0に置き換え、最初に見つかった9未満の桁に1を加えて終了します。見つからなければ、すべての桁が9だったということです。答えは1の後にゼロが続く数です。
解説
数字を数値に変換して1を加え、再び変換する方法ではうまくいきません。100桁の数は、約1.8 × 10^19で上限に達する64ビット整数ではオーバーフローするためです。そこで、筆算と同じように、最後の桁から繰り上がりを使って足します。作業を短縮できる重要な点は、1を加えると変わるのは末尾の9だけで、それらは0になり、その左隣の最初の桁も変わるということです。それ以外の桁はすべてそのままです。
桁ごとに繰り上がりを加える
考え方
学校で習うように、数字を書き下し、一番右の桁の下に 1 を足します。足す数である 1 を繰り上がりとして始めます。右から各桁について、列の合計はその桁の数字と繰り上がりの合計です。その一の位である total % 10 を答えに入れ、十の位である total / 10 を次の列への繰り上がりにします。
繰り上がりが 1 のとき、列の合計は最大でも 9 + 1 = 10 なので、繰り上がりは常に 0 または 1 です。最初の桁の後にも繰り上がりが残っている場合、答えの先頭に新しい桁が加わります。999 + 1 では、1000 の 1 のために 4 桁目が必要です。
答えは、計算する順番がそうなるため、一番右の桁から出てきます。その順に集め、最後に逆順にします。これにかかる時間は O(n) で、新しい配列には最大 n + 1 個の桁が入ります。
アルゴリズム
carryを1に設定し、答えを格納する空のリストを作成します。- 最後の桁から最初の桁まで、各桁について
total = digit + carryを計算します。 total % 10を答えに追加し、carryをtotal / 10を切り捨てた値に設定します。- ループの後、
carryが1なら、それを追加します。 - 答えを逆順にして返します。
def plusOne(digits):
result = [] # the answer, last digit first
carry = 1 # the one you are adding
for i in range(len(digits) - 1, -1, -1):
total = digits[i] + carry
result.append(total % 10)
carry = total // 10
if carry > 0:
result.append(carry)
result.reverse()
return result9未満の最初の数字で停止
考え方
ちょうど1を足したとき、繰り上がりがどうなるかを見てみましょう。9未満の数字は繰り上がりを吸収します。3は4になり、繰り上がりは0になって、それより左にあるすべての桁は値を保ちます。繰り上がりを次に渡すのは9だけで、0に変わります。つまり、1を足すということは、末尾の9を0に変えてから、その直前の桁に1を足すことです。
最後の桁から左へ進みます。9なら0を書き、続けます。9以外の数字なら1増やして、その場で配列を返します。それより左の桁は変わらないからです。[2, 9, 0, 9]の場合、最後の9が0になり、0が1になったところで終了し、最初の2桁を調べることなく[2, 9, 1, 0]になります。
ループで9未満の桁が見つからなければ、すべての桁が9で、それらは0になっています。この数は10^n - 1なので、答えは1の後にn個の0が続く数です。新しい配列が必要なのはこの場合だけです。それ以外は入力をその場で変更するため、追加の空間計算量はO(1)で、ループの実行回数は末尾の9の個数に1を加えた回数です。
アルゴリズム
- インデックスを最後から最初までたどります。
- 桁が9未満なら、1増やして配列を返します。
- そうでなければ、その桁は9です。0にして、1桁左に移動します。
- ループが終了した場合、すべての桁が9だったことになります。1の後に
n個の0が続く値を返します。
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # no carry leaves this digit, so the rest stays as it is
return digits
digits[i] = 0 # 9 + 1 = 10: write 0 and carry one to the left
# Every digit was 9: the answer is 1 followed by zeros.
return [1] + digits
落とし穴と境界ケース
注意すべき落とし穴は、整数オーバーフローと、すべての桁が9の場合です。
- 配列を整数に変換してから戻す方法です。小さなテストには通っても、100桁の数では失敗します。64ビット整数で扱えるのは最大19桁または20桁で、浮動小数点数ではさらに早く末尾の桁が失われます。
- 桁が1つ増える場合を忘れることです。
[9, 9, 9]は4桁の[1, 0, 0, 0]にならなければなりません。既存の桁だけを書き換えるコードでは、[0, 0, 0]が返されます。 - 最後の桁ではなく、最初の桁に1を足すことです。配列では最上位桁が先頭にあるため、1の位は末尾にあります。
- 9未満の桁が繰り上がりを吸収した後に、return するのを忘れることです。早期終了する版では、ループが続いて、本来そのままであるべき桁まで変更してしまいます。
[1, 9, 3]では3だけが変わり、答えは[1, 9, 4]です。 - 配列のインデックスが1から始まるLuaとRで、インデックスの順序を取り違えることです。最後の桁のインデックスは
nで、新しい先頭の1はインデックス1の前に置きます。
よくある質問4
Plus One の時間計算量はどれくらいですか？
どちらの方法も、n 桁に対して時間計算量は O(n) です。最悪の場合はすべての桁が9で、すべての桁に触れるためです。早期終了版は末尾の9の後で停止するため、9未満の桁で終わる数では1ステップで済みます。答えに新しい先頭の桁が必要な場合を除き、追加の領域は O(1) です。
数字を整数に変換しないのはなぜですか？
数値は100桁になる可能性があり、64ビット整数は約1.8 × 10^19、つまり20桁で上限に達するためです。PythonとRubyでは整数に上限がないので変換できますが、これでは練習問題の要点が隠れてしまい、ほかの言語には応用できません。桁ごとに処理すれば、オーバーフローは発生しません。
結果の桁数が入力より多くなるのはいつですか？
すべての桁が9の場合に限ります。そのとき数は10^n - 1となり、1を足すと10^nになります。これは1の後にn個の0が続く数です。9未満の桁が1つでもあれば、その桁が繰り上がりを吸収するため、桁数は変わりません。
数字の配列として格納された2つの数値をどのように足しますか？
最初の方法の桁ごとの計算を使い、各配列の末尾に1つずつインデックスを置きます。各桁では、欠けている桁を0として扱い、2つの数字と繰り上がりを足します。両方の配列を使い切り、繰り上がりが0になるまで続けてから、集めた数字を逆順にします。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def plusOne(digits):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
digits = [4, 3, 9]
期待値
[4, 4, 0]