Steps to Reduce a Number to Zero
0以上の整数 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
- 説明
- 2進数では
123は1111011です。7桁で、1が6つあります。1が6つあるため減算が6回必要で、先頭の1より下の6桁のために半分にする操作が6回必要となり、合計12ステップです。
提出時に隠しテスト+12件
発展問題
奇数は、1 減る代わりに 1 増えることもあるとします。0 に到達するための最少ステップ数はいくつですか。また、15 の場合はどちらを選ぶのが正しいですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
14に規則を手作業で適用して、数えてみましょう。32ビットの数値は何回半分にできますか？数値を2進数で書いてください。半分にすると桁はどうなり、奇数から
1を引くとどうなりますか？1 ビットごとに減算が 1 回必要で、先頭の 1 を除く各 2 進数字ごとに半分にする操作が 1 回必要です。
n == 0は個別に扱います。
解説
この規則を実行するのはすでに高速です。半分にするたびに数は半分になるため、2^31 - 1でさえ必要なステップ数はわずか61です。興味深いのは、この規則が2進数の桁にどのような影響を与えるかを見ることです。半分にすると最後の桁が取り除かれ、奇数から1を引くと、最後の1が0になります。したがって、答えは桁数に1の個数を足し、1を引いた数です。
プロセスを実行する
考え方
文の指示どおりに処理します。n が 0 より大きい間、偶数なら半分にし、奇数なら 1 を引いて、ステップ数を数えます。14 の場合、ループは 7、6、3、2、1、0 の順に訪れ、6ステップです。
引き算をすると奇数は必ず偶数になるため、少なくとも2ステップごとに1回は半分にでき、ループは短くなります。2^31 未満の数は、1 になるまでに半分にする回数が最大でも 30 回です。各回の半分にする処理の前に1回引き算し、最後にもう1回引き算すると、ループの実行回数は最大で 61 回です。
入力が 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進数で見てみましょう。14 は 1110 です。半分にすると最後の桁が落ちて、111 になります。奇数から 1 を引くと最後の桁の 1 が消えて、110 になります。つまり、各ステップで最後の桁を取り除くか、末尾の 1 を 0 に変えるかのどちらかです。
では数えてみましょう。数の中の各 1 は一度ずつ消す必要があり、そのために 1 ごとに減算が1回必要です。各桁を取り除くには、先頭の桁を除き、桁ごとに半減が1回必要です。1 だけが残ったときは、それを消す減算によってすでに 0 になるからです。したがって答えは length - 1 + ones です。14 = 1110 の場合は 4 - 1 + 3 = 6 です。
Java、C、C++、Go、Rust、Swiftには、どちらの個数も数える組み込み関数（先頭のゼロの数と1ビットの数）があり、ほとんどのプロセッサでは単一の命令にコンパイルされます。その他の言語では、n を2進数で表して文字数を数えるか、% 2 で各桁を読み取ります。これは最大でも 31 回のループです。まず n = 0 の場合は 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")
落とし穴と境界ケース
この規則は2行です。間違いは端のケースと、公式の1つずれにあります。
- ビットの公式で
n = 0を忘れる。桁がなく、1もない場合、length - 1 + onesは-1になり、先行ゼロの数0は未定義の場合があります（Cの__builtin_clz(0)）。 - 先頭の桁を半分にする回数に数える。
1は減算によって0になるため、8 = 1000に必要なステップは5ではなく4 - 1 + 1 = 4です。 - 2つのステップを1つにまとめる。奇数に対して
n = (n-1) / 2と書くと、減算と半分にする処理を同時に行うため、カウントに加えるのは1ではなく2です。そうしないと、14の結果は6ではなく4になります。 n > 1の間ループする。最後のステップで1が0になるため、これでは1ステップ早く終了します。ループはnが0になるまで実行する必要があります。
よくある質問4
数をゼロに減らす時間計算量はどれくらいですか？
このプロセスの実行時間は O(log n) です。少なくとも2ステップごとに数が半分になるためです。n = 2^31 - 1 の場合、61 ステップです。組み込みのビット命令で2進数の桁数を数える処理は O(1) です。
ステップ数の公式は何ですか？
n > 0の場合、答えはnを2進数で表したときの桁数から1を引き、さらに1ビットの数を加えたものです。1ビットごとに1回の減算が必要で、先頭の1より下にある各桁ごとに1回の半減が必要です。n = 0の場合、答えは0です。
2^31未満の数のうち、最も多くのステップを要するのはどれですか？
2^31 - 1は、2進数で1が31個並んだ数です。合計で61ステップ、つまり31回の引き算と30回の半分への操作が必要です。これより小さい数で、桁数と1の個数が同時にこれほど多いものはありません。
なぜ半分にすることは右シフトと同じなのでしょうか？
2進数は2の累乗の和です。偶数を2で割ると、すべての累乗が1つ下がり、各桁が右に1つ移動して、最後の0が取り除かれます。これはまさにn >> 1が行うことなので、どちらの方法でも半分にできます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def numberOfSteps(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 14
期待値
6