Plus One
負でない整数が、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です。
発展問題
1以上の数について、代わりに1を引くにはどうすればよいでしょうか？ [1, 0, 0]のように、結果の先頭の桁がなくなるのはどんなときでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数は100桁になることもあり、組み込みの整数型では扱いきれません。筆算のように、桁ごとに足し算をしましょう。まず、1はどこに行きますか？
9 未満の桁に 1 を足しても繰り上がりは発生しないため、左側の桁は変わりません。9 の場合だけ 0 になり、繰り上がりが伝わります。
最後の桁から左へ進みます。各9を0にします。9未満の桁が初めて見つかったら、1を足して終了します。見つからなければ、すべての桁が9です。答えは1の後に0を並べたものです。
解説
100桁の数は、約1.8 × 10^19で上限に達するすべての64ビット整数でオーバーフローするため、変換して足すことはできません。筆算と同じように、最後の桁から繰り上がりを使って足します。1を足すと、末尾の9だけが0に変わり、その左隣の桁も変わります。
桁ごとに繰り上がりを使って足す
考え方
加算する数である1を繰り上がりとして始めます。右から各桁について、列の合計はその桁と繰り上がりの和です。total % 10を答えに入れ、total / 10を次の繰り上がりにします。合計は最大でも9 + 1 = 10なので、繰り上がりは0または1です。最初の桁の後に繰り上がりが残っている場合は、999 + 1 = 1000のように、新しい先頭の桁になります。
答えは最後の桁から順に作るため、その順に集め、最後に逆順にします。計算時間は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未満の最初の数字で停止する
考え方
9未満の桁は繰り上がりの1を吸収します。つまり、その桁は1増え、左側の桁はすべて値が変わりません。繰り上がりを次に渡すのは9だけで、0に変わります。したがって、最初に見つかった9未満の桁で処理を止め、入力配列をその場で変更して返せます。[2, 9, 0, 9]の場合、最後の9が0になり、0が1になるので、最初の2桁を読み取ることなく[2, 9, 1, 0]を返します。
9未満の桁がない場合、その数は10^n - 1で、答えは1の後にn個の0が続く数です。新しい配列が必要なのはこの場合だけなので、それ以外では追加の領域はO(1)です。
アルゴリズム
- インデックスを最後から最初までたどります。
- 桁が9未満なら、1増やして配列を返します。
- そうでなければ、その桁は9です。0にして、左へ1つ移動します。
- ループが終了した場合、すべての桁が9でした。1の後に
n個のゼロを続けて返します。
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
落とし穴と境界ケース
- 配列を整数に変換してから、再び配列に戻す。64ビット整数で保持できるのは最大19桁または20桁なので、100桁ではオーバーフローし、浮動小数点数ではそれより早く末尾の桁が失われます。
- 桁が1つ増えることを忘れる。
[9, 9, 9]は[1, 0, 0, 0]にならなければなりません。既存の桁だけを書き換えるコードでは、[0, 0, 0]が返されます。 - 先頭の桁に1を加える。配列は最上位桁が先頭なので、1の位は最後の要素です。
- 9未満の桁が繰り上がりを吸収した後も戻らない。その後ループが、本来そのままであるべき桁まで変更してしまいます。
[1, 9, 3]は[1, 9, 4]にならなければなりません。 - LuaとRでは配列のインデックスは1から始まるため、最後の桁のインデックスは
nであり、n - 1ではありません。
よくある質問3
Plus One の時間計算量は何ですか？
どちらの方法も、n 桁に対して実行時間は O(n) です。すべてが9の場合、すべての桁に触れるためです。早期終了するバージョンは、末尾の9の処理後に停止し、新しい先頭の桁が必要な場合を除いて、追加の領域を O(1) 使用します。
数字を整数に変換しないのはなぜですか？
その数は100桁になることがあり、64ビット整数は約1.8 × 10^19、つまり20桁で上限に達します。PythonとRubyでは整数に上限がないため変換は機能しますが、そのコードは他の言語にはそのまま使えません。桁ごとに処理すれば、オーバーフローは決して起こりません。
数字の配列として格納された2つの数値をどのように加算しますか？
各配列の末尾に1つのインデックスを置く列方式を使います。各列では、桁がない場合は0として、2つの桁と繰り上がりを加算します。両方の配列を使い切り、繰り上がりが0になったら終了し、集めた桁を逆順にします。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def plusOne(digits):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
digits = [4, 3, 9]
期待される出力
[4, 4, 0]