Count Digits
非負整数 n が与えられたとき、先頭にゼロを付けずに10進数で表した場合の桁数を返してください。ゼロは 0 一文字で表すため、桁数は1です。
関数
- ninteger
- 測定する非負整数
- 戻り値integer
- n の小数桁数
制約
0 ≤ n ≤ 231-1
例
- 入力
- n = 4096
- 出力
- 4
- 説明
- 10で整数除算すると、
4096は409、40、4となります。3桁が取り除かれて1桁が残るので、答えは4です。
- 入力
- n = 0
- 出力
- 1
- 説明
0は1桁で書かれます。数値が0より大きい間カウントするループは、ここでは一度も実行されず、1ではなく0を返します。
- 入力
- n = 100
- 出力
- 3
- 説明
- ゼロも数字です。
100は1、0、0と書くので、答えは3です。
発展問題
たとえば、10の累乗を二分探索することで、各桁ごとに1回実行されるループを使わずに桁数を数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数を10で割って余りを捨てると、桁数はどうなりますか？
10で整数除算するたびに、末尾から数字がちょうど1桁取り除かれます。1桁になるまでに何回除算が必要か数えましょう。
カウンターを1から始め、数が10以上の間は10で割り、そのたびに1を加えます。1から始めることで、
0の場合も正しい答えになります。
解説
10で整数除算するたびに、桁が1つ取り除かれます。1桁になるまで除算の回数を数え、その桁の分として1を加えます。バグは境界に潜んでいます。0は1桁であり、対数の公式は0や、10の大きな累乗を少し下回る値ではうまく機能しません。
数字をテキストとして書き、文字数を数える
考え方
使用している言語では、nはすでに10進数で表されます。その文字列を取得して文字数を数えます。4096は"4096"となり4文字、0は"0"となるため、ゼロに特別な処理は必要ありません。
変換では桁ごとに1回除算するため、時間計算量も追加のメモリ使用量もO(log n)で、この場合は最大10文字です。
アルゴリズム
- 科学表記に切り替わらない関数を使って、
nを10進数の文字列に変換します。 - 文字列の文字数を数えます。
- その数を返します。
0の場合、文字列は"0"なので、追加の確認なしで答えは1です。
def countDigits(n):
return len(str(n))1桁になるまで10で割る
考え方
カウントを1から始め、n ≥ 10である間、10で割るたびに1を加えます。1から始めることで、すべての数に少なくとも1桁あることを表せます。これは0にも当てはまるため、別途チェックする必要はありません。
ループは2147483647の場合でも最大9回実行されます。時間計算量はO(log n)です。カウンターを1つ保持し、nのコピーを変更するため、追加の空間計算量はO(1)です。
アルゴリズム
- 常に存在する桁のために、
count = 1を設定します。 n ≥ 10である間、nを整数除算で10で割り、countに1を加えます。- 桁が1つ残ったら、
countを返します。
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
落とし穴と境界ケース
n > 0の間、0から数えます。n = 0の場合は0を返します。floor(log10(n)) + 1を使います。対数がマイナス無限大になる0の場合と、倍精度の丸めによって対数がちょうど15となり、式が16桁と判定する10^15-1の場合は正しく動作しません。- JavaScript、Lua、PHP、またはRでの実数除算では、
/は小数部分を保持します。そのため、n > 0の間ループすると、4096の場合は328回実行されます。Math.floor、math.floor、intdiv、または%/%を使ってください。 - 文字列版での科学表記です。Rでは
as.character(1e5)は"1e+05"となるため、sprintf("%.0f", n)を使ってください。Lua 5.3以降では、tostring(4096.0)は.0を保持するため、string.format("%d", n)を使ってください。
よくある質問3
桁数を数える時間計算量はどれくらいですか？
数値 n の桁数は floor(log10(n)) + 1 であり、ループは桁ごとに1回除算を行うため、実行時間は O(log n)、空間計算量は O(1) です。32ビット整数の場合、最大でも10ステップです。
log10を使って数値の桁数を数えられますか？
正のnの場合、桁数はfloor(log10(n)) + 1ですが、対数は浮動小数点数で計算されます。0では未定義であり、10の累乗に近い値では丸め誤差によって誤った結果になることがあります。倍精度ではlog10(10^15-1)はちょうど15になります。整数除算は常に正確です。
負の数の桁数はどのように数えますか？
まず絶対値を取り、その後は通常どおり数えます。String(-42)は、マイナス記号が数字ではないため、3文字です。最小の32ビット整数の場合は、32ビットには収まらないため、64ビット型で絶対値を取ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countDigits(n):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
n = 4096
期待される出力
4