Steps to Reduce a Number to Zero
負でない整数 n から始め、0 に達するまで次の規則を繰り返します。数が偶数なら 2 で割り、奇数なら 1 を引きます。規則を適用するたびに1ステップと数えます。かかるステップ数を返してください。
関数
- ninteger
- 開始数
- 戻り値integer
- 数が0になるまでのステップ数
制約
0 ≤ n ≤ 231 - 1
例
- 入力
- n = 14
- 出力
- 6
- 説明
- 数値は
14 → 7 → 6 → 3 → 2 → 1 → 0と進みます。半分にする操作が3回、引き算が3回で、合計6ステップです。
- 入力
- n = 8
- 出力
- 4
- 説明
8 → 4 → 2 → 1 → 0。2の累乗は3回半分になり、最後に1回の減算が必要です。4ステップです。
- 入力
- n = 123
- 出力
- 12
- 説明
- 二進数では
123は1111011です。7桁で、1が6つあります。6つの1には6回の減算が必要で、先頭の1より下にある6桁には6回の半分化が必要なので、合計12ステップです。
発展問題
奇数も1増やせるとします。0に到達するための最小のステップ数はいくつですか。また、15の場合、どの選択が正しいですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
14にルールを手で適用して、数えてみましょう。32ビット数は何回半分にできますか？数値を2進数で書いてください。半分にすると桁はどうなりますか。また、奇数から
1を引くとどうなりますか？1 ビットごとに減算が 1 回必要で、先頭の 1 を除く各 2 進数の桁ごとに半分にする操作が 1 回必要です。
n == 0は個別に扱います。
解説
2進数では、半分にすると最後の桁が落ち、奇数から 1 を引くと最後の 1 が 0 に変わります。したがって、n > 0 の場合、答えは2進数の桁数に1の個数を加え、1を引いた数です。このルールをそのまま実行しても高速で、ステップ数は最大でも 61 です。
プロセスを実行する
考え方
規則を実行して、ステップ数を数えましょう。14の場合、ループは7、6、3、2、1、0の順に処理します。6ステップです。
引き算をすると、奇数は必ず偶数になるため、少なくとも2ステップに1回は半分になります。2^31未満の数は、1に達するまでに最大30回半分になります。各回の半分にする処理の前に1回引き算し、最後にも1回引き算するので、ループは最大61回実行されます。n = 0の場合、ループは一度も実行されず、答えは0です。
アルゴリズム
stepsを0に設定します。n > 0の間、nが偶数ならnをn / 2に設定し、そうでなければn-1に設定します。- 毎回、
stepsに1を加えます。 stepsを返します。
def numberOfSteps(n):
steps = 0
while n > 0:
if n % 2 == 0:
n //= 2
else:
n -= 1
steps += 1
return steps2進数の桁数を数える
考え方
各ステップでは、最後の2進数の桁を削除するか、末尾の1を0にします。14は1110です。半分にすると111になり、111から引くと110になります。すべての1を一度ずつ消す必要があり、そのために1ごとに1回の減算が必要です。先頭の1を除くすべての桁を削除する必要があり、それぞれ1回の除算が必要です。1だけが残ったときは、その減算ですでに0になるためです。したがって、答えはlength - 1 + onesであり、14の場合は4 - 1 + 3 = 6です。
Java、C、C++、Go、Rust、Swiftには、両方の数（先行するゼロとセットされたビット）を数える組み込み機能があり、ほとんどのプロセッサでは単一の命令にコンパイルされます。それ以外の言語では、最大31回のループで% 2を使って各桁を調べます。まずn = 0を処理してください。公式の基準となる1ビットがないためです。
アルゴリズム
n == 0の場合は、0を返します。length（nの2進数の桁数）を求めます。ones（1ビットの数）を求めます。length - 1 + onesを返します。
def numberOfSteps(n):
if n == 0:
return 0
# Every bit below the leading one costs a halving,
# and every 1 bit costs a subtraction.
return n.bit_length() - 1 + bin(n).count("1")
落とし穴と境界ケース
- ビットの公式で
n = 0を忘れること。length - 1 + onesは-1になり、先行ゼロの数は0の場合に未定義になることがあります（Cの__builtin_clz(0)）。 - 先頭の桁を半減させる回数に数えること。減算によって
1は0になるため、8 = 1000に必要なステップ数は5ではなく4 - 1 + 1 = 4です。 - 奇数に対して
n = (n-1) / 2と書き、1ステップとして数えること。この行では2ステップ進むため、14の結果は6ではなく4になります。 n > 1の間ループすること。これでは最後のステップ、つまり1を0にする処理の前に停止してしまいます。
よくある質問3
数値をゼロにする時間計算量はどれくらいですか？
この処理の実行には O(log n) 時間がかかります。少なくとも1ステップおきに数が半分になるためです。n = 2^31 - 1 の場合は 61 ステップです。組み込みのビット命令で2進数の桁数を数える処理は O(1) です。
2^31未満で最も多くのステップを要する数はどれですか？
2^31 - 1は、二進数で1が31個並んだ数です。31回の減算と30回の半分への除算が必要で、合計61ステップです。これより小さい数で、これほど多くの桁数と1を同時に持つものはありません。
なぜ半分にすることは右シフトと同じなのですか？
2進数は、2の累乗の和です。偶数を2で割ると、すべての累乗が1つ下がり、すべての桁が右に1つ移動して、最後の0が取り除かれます。これはn >> 1が行うことなので、どちらの方法でも半分にできます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def numberOfSteps(n):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
n = 14
期待される出力
6