Sum of Digits
0以上の整数 n が与えられます。その10進数の各桁の合計を返してください。たとえば、482 の各桁は4、8、2なので、答えは 14 です。
関数
- ninteger
- 各桁を足し合わせる、0以上の整数
- 戻り値integer
- n の各桁の数字の合計
制約
0 ≤ n ≤ 231-1
例
- 入力
- n = 9045
- 出力
- 18
- 説明
9045の各桁は9、0、4、5で、9 + 0 + 4 + 5 = 18です。0は何も加えませんが、それでも1桁として数えます。
- 入力
- n = 7
- 出力
- 7
- 説明
- 1 桁の数はその数自身が各桁の合計なので、
7は7になります。
提出時に隠しテスト+15件
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
算術演算を1回行うだけで、数値の最後の桁を求めるにはどうすればよいでしょうか？
最後の桁は
n % 10で、10による整数除算でそれを取り除きます。この2つの操作を1組行うごとに、1桁が得られます。合計を累積します。
nが 0 より大きい間、n % 10を合計に加え、nを 10 で割って切り捨てます。
解説
数値は各桁を一つずつ渡してくれるわけではないため、自分で取り出す必要があります。文字列に変換して文字を読み取る方法もあれば、最後の桁を取り出す2つの算術操作を使う方法もあります。n % 10で最後の桁を得て、10による整数除算でそれを取り除きます。どちらの方法も桁ごとに1ステップかかり、以下では桁数をdと表し、ここではd ≤ 10です。算術演算を使う方法では追加のメモリは必要ありません。
数字をテキストとして読み取る
考え方
数値を書き留めるとき、すでにその桁を目にしています。nを10進数の文字列に変換すると、9045は9、0、4、5の4文字になります。次に、各文字を順に見て、それぞれの値を加算します。
文字は、まだ数値ではありません。文字'4'はコード52として格納されるため、解析するか、'0'のコードを引きます。つまり、'4' - '0' = 4です。数字の文字はコードが連続しているので、この減算は10個すべての数字で機能します。
テキストには数字1桁につき1文字、合計d文字があるため、ループにはO(d)の時間がかかり、テキスト自体には追加でO(d)の領域が必要です。
アルゴリズム
nを10進数の文字列に変換します。total = 0を設定します。- 各文字について、その数字の値を
totalに加算します。 totalを返します。
def sumOfDigits(n):
total = 0
for digit in str(n):
total += int(digit)
return total% 10 で最後の桁を取り出す
考え方
テキストを使わずに数値を分解できます。10で割った余りが最後の桁です：9045 % 10 = 5。10で整数除算すると、その桁が取り除かれます：小数部分を切り捨てると、9045 / 10 = 904 になります。この操作を繰り返すと、右から左へ桁を取り出せます。
9045 の場合：5を加えて904を残し、4を加えて90を残し、0を加えて9を残し、9を加えて0を残します。合計が18になると、ループは0で停止します。n = 0 の場合、ループは一度も実行されず、答えは0です。これは正しい結果です。
各ステップで桁が1つ取り除かれるため、ステップ数は d、時間計算量は O(d) です。また、メモリ上に保持する整数は2つだけなので、空間計算量は O(1) です。中間値はすべて n より小さいため、オーバーフローは発生しません。
アルゴリズム
total = 0に設定します。n > 0の間、n % 10をtotalに加えます。nを10で割り、小数部分を切り捨てます。nが0になったら、totalを返します。
def sumOfDigits(n):
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop the last digit
return total
落とし穴と境界ケース
ループは短く、間違いは型と最小の入力に関するものです。
- 言語で実数除算を意味するところで
/を使う。JavaScript、TypeScript、Lua、PHP、Rでは、9045 / 10は904.5となり、ループはその後、小数を加算します。Math.floorまたはmath.floorで切り捨てます。Pythonでは//、Dartでは~/、PHPではintdiv、Rでは%/%を使います。 - 数字ではなく文字を加算する。文字
'7'のコードは7ではなく55です。'0'を引くか、先に文字を解析します。 n >= 10の間ループする。すると、先頭の桁がnに残ったままループが終了し、その桁は加算されないため、9045は18ではなく9になります。n > 0の間ループすれば、n = 0の場合も0を返します。- Rで大きな数値をテキストとして出力する。
as.character(100000)は、数値の6桁ではなく"1e+05"を返します。format(n, scientific = FALSE)を使います。
よくある質問4
数値の各桁を合計する時間計算量はどれくらいですか？
1桁につき1ステップなので、O(d)です。ここで、dは桁数です。数値nの桁数はおよそlog10(n) + 1なので、同じ計算量はしばしばO(log n)と表記されます。32ビット整数の場合、最大で10ステップです。
数値を文字列に変換せずに、その桁を取り出すにはどうすればよいですか？
剰余と10による整数除算を使います。n % 10は最後の桁で、余りを切り捨ててnを10で割ると、その桁が取り除かれます。nが0になるまで繰り返すと、右から左へすべての桁を順にたどれます。
数の数字根とは何ですか？
1桁になるまで数字を何度も足し合わせて得られる値です。9045の場合、18になり、さらに9になります。正のnについては、どの数も9で割ったとき、各桁の数字の合計と同じ余りになるため、1 + (n-1) % 9と等しくなります。
文字列版と算術版では、どちらのほうが優れていますか？
どちらも O(d) で、どちらも正解です。文字列を使う方法は多くの言語で短く書けますが、数字のコピーを作成します。算術演算を使う方法は追加メモリを O(1) しか使わず、% 10 と / 10 で数値を分解する方法を知っていることを面接官に示せます。この知識は、回文や数字の反転の問題でも役立ちます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def sumOfDigits(n):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 9045
期待値
18