https://leetcode.com/problems/sqrtx/description/
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
- For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
Constraints:
- 0 <= x <= 231 - 1
영 찝찝한 overflow...!
1. C
int mySqrt(int x) {
if(x==0) return 0;
int l = 1;
long long r = x;
int ans = 0;
while(l<=r){
long long mid = 0.5*(l+r);
if(mid <= x/mid){
ans = mid;
l = mid+1;
}else{
r = mid-1;
}
}
return ans;
}
2. Python
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0 : return 0
l = 0
r = x
ans = 0
while l <= r:
mid = int(0.5*(l+r))
if mid * mid <= x :
ans = mid
l = mid+1
else :
r = mid-1
return ans
3. C++
class Solution {
public:
int mySqrt(int x) {
if(x==0) return 0;
int l = 0;
int r = x;
long ans;
while(l<=r){
long mid = 0.5*(l+r);
if(mid*mid<=x){
ans = mid;
l = mid+1;
}else{
r = mid-1;
}
}
return ans;
}
};