Square Root (Integer)
関数は非負整数 x を受け取り、その整数平方根を返します。つまり、r × r ≤ x を満たす最大の整数 r です。これは平方根を切り捨てた値なので、完全平方数ではない数の場合、その数より小さい最大の完全平方数の平方根を返します。組み込みの平方根関数や累乗関数を使わずに、自分で計算してください。
関数
- xinteger
- 平方根を求める非負の整数
- 戻り値integer
- x の平方根を整数に切り捨てた値
制約
0 ≤ x ≤ 231 - 1- 組み込みの平方根関数、べき乗関数、または指数関数を呼び出さないでください。
例
- 入力
- x = 17
- 出力
- 4
- 説明
4 × 4 = 16は 17 以下ですが、5 × 5 = 25は 17 を超えるため、17 の平方根は切り捨てて 4 になります。
- 入力
- x = 49
- 出力
- 7
- 説明
- 49は平方数です。
7 × 7 = 49なので、丸めは行われず、答えは正確に7です。
提出時に隠しテスト+17件
発展問題
代わりに整数の立方根、つまり x が負の場合もあるとして、r × r × r ≤ x を満たす最大の r をどのように求めますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
答えは、2乗すると
x以下になる最大の整数です。候補のmを2乗してxと比較すると、mより小さい候補と大きい候補について何がわかりますか？mが大きくなるにつれて、平方数も大きくなります。m × m ≤ xなら、それより小さい候補もすべて条件を満たします。m × m > xなら、それより大きい候補はすべて条件を満たしません。候補は条件を満たすものが並んだ後に、満たさないものが続く順序になっており、二分探索でその切り替わり位置を見つけられます。0から
xまでの範囲でmを探索します。m × m ≤ xの場合はmを記録して右側を探索し、そうでない場合は左側を探索します。最初のmは約10^9になることがあるため、64ビット整数でmを2乗します。
解説
0から数え上げて、次の平方数がxを超えるまで続ければ正しい答えが得られますが、平方根の値に相当する回数だけ処理を繰り返す必要があり、範囲の上限付近では約46000回になります。0、1、4、9、16などの平方数は昇順に並んでいるため、平方がx以下となる最後の候補を二分探索すれば、約31回で完了できます。どちらの場合にも落とし穴となるのはオーバーフローです。候補の平方が常に32ビットに収まるとは限りません。
ゼロから数え上げる
考え方
平方根は、r × r ≤ xを満たす最大のrです。平方は常に条件を満たすr = 0から始め、次の数の平方がまだ条件を満たす間、r + 1ずつ増やしていきます。次の数が大きすぎる最初のrでループが停止し、それがちょうど平方根です。x = 17の場合、1、4、9、16の平方は条件を満たしますが、25は満たさないため、ループは4で停止します。
ループは答えの値だけ繰り返されます。この場合、答えの最大値は46340なので、ステップ数は最大でも46340回で、すぐに終わります。ただし、計算量はO(√x)で、入力が大きくなるほど増加します。64ビットのxでは、約3 × 10^9ステップかかる可能性があります。
最後のチェックに注意してください。x = 2^31 - 1の場合、ループは大きすぎることを確認するために46341を二乗しますが、46341 × 46341 = 2147488281は32ビット整数に収まりません。二乗は64ビットで行いましょう。
アルゴリズム
root = 0に設定します。(root + 1) × (root + 1) ≤ xの間、rootを1増やします。rootを返します。
def mySqrt(x):
root = 0
while (root + 1) * (root + 1) <= x:
root += 1
return root答えに対する二分探索
考え方
候補の 0、1、2 から x までを並べ、それぞれに同じ質問をします。その数の平方は x 以下ですか？平方は大きくなる一方なので、答えは「はい」「はい」「はい」と続き、平方根を超えた候補はすべて「いいえ」になります。平方根は最後の「はい」です。「はい」が続いたあとに「いいえ」が続く並びは、二分探索にぴったりです。
まだ判定していない候補の範囲 lo から hi を、最初は 0 から x として保持し、これまでで最大の「はい」である best という変数も用意します。中央の mid を調べます。mid × mid ≤ x なら、平方根は mid 以上です。これを best に格納し、lo を mid + 1 に移します。そうでなければ、平方根はもっと小さいので、hi を mid - 1 に移します。範囲が空になったら、best が平方根です。
x = 17 の場合を追ってみましょう。範囲 0 から 17 では 8 を調べます（64、大きすぎる）。次に 0 から 7 では 3 を調べます（9、条件に合うので best = 3）。続いて 4 から 7 では 5 を調べます（25、大きすぎる）。最後に 4 から 4 では 4 を調べます（16、条件に合うので best = 4）。範囲が空になり、答えは 4 です。各ステップで範囲は半分になるため、x = 2^31 - 1 でも 31 ステップで済みます。平方の計算は 64 ビットで行いましょう。この場合、最初の mid は 1073741823 です。
アルゴリズム
lo = 0、hi = x、best = 0を設定します。lo ≤ hiの間、範囲の中央であるmidを計算します。mid × mid ≤ x（64ビット）なら、best = mid、lo = mid + 1を設定します。- そうでなければ、
hi = mid - 1を設定します。 bestを返します。
def mySqrt(x):
lo, hi = 0, x
best = 0 # largest candidate seen so far whose square fits
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
best = mid # mid fits, so try a larger root
lo = mid + 1
else:
hi = mid - 1 # mid is too big
return best
落とし穴と境界ケース
探索自体は短いですが、バグは算術処理と境界に潜んでいます。
- 32 ビットでの二乗。
x = 2147483647の場合、最初の中央候補は 1073741823 で、その二乗は約1.15 × 10^18です。32 ビットのintでは値がオーバーフローして誤った値になり、小さすぎて範囲内に収まるように見えることさえあります。乗算を 64 ビットで行うか、代わりにm ≤ x / mと比較してください。 - カウントループで次の候補を 32 ビットで二乗すること。
2^31 - 1の平方根は 46340 で、ループの最後のチェックでは 46341 を二乗するため、結果は 2147488281 となり、32 ビットの上限を超えます。 - 範囲を 32 ビットを超えて広げること。排他的な上限
hi = x + 1は、最大のxに対して 2147483648 となり、32 ビットの上限を 1 超えます。包含的なhi = xを使うと、最初のステップでlo + hiはちょうど 2147483647 となるため、余裕はありませんが収まります。64 ビットのインデックスを使うか、lo + (hi - lo) / 2を使ってください。 - 条件に適合した最後の値ではなく、最後に調べた
midを返すこと。x = 17の場合、探索は大きすぎる 5 を調べた後に終了します。答えは記憶しておいた 4 です。 - 小さい値のケースを壊してしまうこと。
lo = 1から始める探索ではx = 0を見落とし、また、除算によるチェックm ≤ x / mはm = 0のときゼロ除算になります。0 と 1 は個別にテストしてください。
よくある質問4
組み込み関数を使わずに平方根を求めるにはどうすればよいでしょうか？
整数の平方根を求めるには、二分探索で答えを探します。候補である 0 から x までは、平方が x 以下となる範囲と、それより大きくなる範囲に分かれており、二分探索で前者の最後の候補を見つけます。もう一つよく使われる方法はニュートン法です。推定値 r を (r + x / r) / 2 で更新し、平方が条件に合うまで繰り返します。
二分探索による平方根計算の時間計算量はどれくらいですか？
O(log x)時間、O(1)空間です。各ステップで候補の範囲が半分になるため、x = 2^31 - 1では31ステップ必要です。0から数え上げる方法では、同じxに対してO(√x)ステップ、つまり46340ステップかかります。ここでは問題ありませんが、64ビットの入力ではすぐに増加します。
ニュートン法では、整数平方根をどのように計算しますか？
r = x から始めます。r × r > x の間、整数除算を使って r を (r + x / r) / 2 に置き換えます。各ステップで r は根を通り越すことなく近づくように小さくなり、ループは平方根の整数部分で停止します。x = 2^31 - 1 の場合、19 ステップ必要で、近づいてからはステップごとに正しい桁数がおよそ 2 倍になります。
答えが32ビットに収まるのに、なぜ解答には64ビット整数が必要なのですか？
答えは最大でも46340ですが、試す候補はそうではありません。0からxまで二分探索すると、最初に10^9に近い候補を試し、その二乗は10^18に近く、約2.1 × 10^9という32ビットの上限を大幅に超えます。64ビットで二乗すれば、比較を正確に行えます。m ≤ x / mと比較すれば、大きな積をまるごと避けられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def mySqrt(x):
# ここにコードを書いてくださいケース1
ケース2
入力
x = 17
期待値
4