こちらは「Sqrt」のPythonによる解答例となっております。この問題は、非負整数xが与えられたときに、xの平方根を整数で返す問題です。
問題
非負整数 x が与えられたとき、x の平方根を整数で返します。整数部分のみを返す必要があります。小数部分は切り捨てます。
0 <= x <= 2^31 – 1
解法
この問題は、二分探索を用いた1つのアプローチがあります。二分探索は、範囲を狭めながら目的の値を探索するアルゴリズムであり、この問題に適しています。
アルゴリズムの概要を以下に述べます。
- xの平方根は、0からxの半分の間に存在するため、この範囲を初期値として設定します。
- 二分探索を実行します。
- 中央値を計算し、中央値の2乗がxよりも大きければ、中央値よりも小さい範囲で再検索します。
- 中央値の2乗がxよりも小さければ、中央値よりも大きい範囲で再検索します。
- 探索を繰り返し、最後に見つかった中央値を返します。
Pythonコード
以下のコードが、「Sqrt」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().mySqrt
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.x)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
### return (x**0.5)//1
lo, hi = 0, x
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid > x:
hi = mid - 1
elif mid * mid < x:
lo = mid + 1
else:
return mid
return hi
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.x = 4
self.ans = 2
elif num == 2:
self.x = 8
self.ans = 2
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################