Count Digits
非負整数 n を受け取り、先頭にゼロを付けずに10進数で表したときの桁数を返す関数を書いてください。ゼロは 0 の1桁で表されるため、桁数は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です。
提出時に隠しテスト+16件
発展問題
たとえば、10の累乗に対する二分探索を使って、桁数分だけ繰り返すループを使わずに桁数を数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数を10で割って余りを捨てると、桁数はどうなりますか？
10で整数除算するたびに、末尾からちょうど1桁が取り除かれます。1桁になるまでに何回除算する必要があるか数えましょう。
カウンターを1から始め、数が10以上の間は10で割り、そのたびに1を加えます。1から始めることで、
0に対しても正しい答えが得られます。
解説
桁数とは、1桁が残るまで10で割ることのできる回数に、その1桁を加えたものです。考え方は1行で表せますが、注意すべき点は端のケースです。0は1桁で、桁数は9と10の間で変わります。また、対数に基づく式は0で破綻し、浮動小数点演算では大きな10の累乗を少し下回る値でも破綻します。
数値をテキストとして記述し、文字数を数える
考え方
あなたの言語には、すでにnを10進数で表記する方法があります。その文字列を取得して文字数を数えます。4096は"4096"となり、4文字です。0は"0"となり、1文字なので、ゼロに特別な処理は必要ありません。
ライブラリ内部では、各桁につき1回、10で割るため、処理量はO(log n)です。文字列には各桁につき1文字が格納されるので、追加メモリ量はO(log n)で、ここでは最大10文字です。
書式は通常の10進数でなければなりません。Rでは、as.character(1e5)は"1e+05"を返し、6桁の数値が5文字になるため、sprintf("%.0f", n)で書式を指定します。Lua 5.3以降では、tostring(4096.0)は.0を保持しますが、string.format("%d", n)なら、どのバージョンでも整数として出力されます。
アルゴリズム
- 科学的記数法に切り替わらない関数を使って、
nを10進数の文字列に変換します。 - 文字列の文字数を数えます。
- その数を返します。
0の場合、文字列は"0"なので、追加のチェックなしで答えは1です。
def countDigits(n):
return len(str(n))1桁になるまで10で割る
考え方
10 で整数除算すると最後の桁が取り除かれます。4096 / 10 は 409 です。除算するたびに桁が1つ減るため、1桁になるまでに必要な除算回数に、最後の1桁分として1を加えたものが答えです。4096 は3回の除算が必要なので（409、40、4）、4桁です。
カウントを1から始め、n ≥ 10 の間は除算します。1から始めることで、すべての数は少なくとも1桁あることを示します。これは 0 に対する規則そのものです。よく最初に書かれる、0から始めて n > 0 の間カウントする方法では、n = 0 のとき 0 が返され、別途チェックが必要になります。
ループは最初の桁以降の桁ごとに1回実行され、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では対数が負の無限大になるため失敗します。また、10の累乗よりわずかに小さい大きな値でも失敗します。倍精度ではlog10(10^15-1)がちょうど15に丸められるため、この式は15桁ではなく16桁だと判定します。n > 0の間実行されるループで、実数の除算を使う方法。JavaScript、Lua、PHP、Rでは、/は小数部分を保持するため、4096は0に達するまでに328ステップかけて0に近づきます。Math.floor、math.floor、intdiv、または%/%を使いましょう。- 文字列に変換する方法で科学表記を使うこと。Rでは
100000は"1e+05"と出力されます。 - マイナス記号を桁として数えること。この問題の入力は負の数にはなりませんが、
String(-42)は3文字なので、負の数にも対応するバージョンでは、先に絶対値を取ります。
よくある質問4
数値を文字列に変換せずに、桁数を数えるにはどうすればよいですか？
1桁になるまで整数除算で10で割り、割った回数を数えて、最後の桁の分として1を加えます。4096は409、40、4となります。3回割るので、4桁です。このループが使用する追加領域はO(1)です。
なぜ 0 は 1 桁なのですか？
ゼロは1文字の0で表記されるため、その10進表記は1桁です。数が0より大きい間、除算の回数を数えるコードは、0の場合は一度も実行されず、0を返します。カウンターを1から始め、数が10以上の間除算することで、特別な場合分けなしで処理できます。
log10 を使って数値の桁数を数えられますか？
正のnの場合、桁数はfloor(log10(n)) + 1ですが、対数は浮動小数点数で計算されます。0では定義されず、10の累乗に近い値では丸め誤差が生じ、誤った結果になることがあります。倍精度ではlog10(10^15-1)はちょうど15になります。整数除算なら常に正確な答えが得られます。
桁数を数える時間計算量はどれくらいですか？
数値 n は floor(log10(n)) + 1 桁であり、ループは各桁につき1回除算を行うため、実行時間は O(log n) です。32ビット整数の場合、最大でも10ステップです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def countDigits(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 4096
期待値
4