説明#
int sqrt(int x) 関数を実装します。
非負整数 x の平方根を計算して返します。
返り値の型が整数であるため、結果は整数部分のみ保持され、小数部分は切り捨てられます。
例 1:
入力: 4
出力: 2
例 2:
入力: 8
出力: 2
説明: 8の平方根は2.82842...であり、
返り値の型が整数であるため、小数部分は切り捨てられます。
アプローチ#
- 無駄な暴力解法、1 から始めて自乗を求め、結果が x より大きい場合はその値を出力し、1 を減らす
int mySqrt(int x){
for(long i=1;;i++) {
if(i*i > x)
return (int)i-1;
}
}
アプローチ 2#
- 前述の方法に加えて、自増のスパンを増やし、広い範囲を探索し、最終値を逆順に探索する
int mySqrt(int x){
long first = 1;
for(;first < x;first *= 2)
if(first * first >= x)
break;
for(long second = first;;second--)
if(second * second <= x)
return second;
}