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.
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 - 1program main
implicit none
integer :: x, y
x = 4
y = sqrt(x)
print '(I0)', y
x = 8
y = sqrt(x)
print '(I0)', y
contains
pure integer function sqrt(x) result(y)
implicit none
integer, value :: x
integer :: i, j
if (x == 0) then
y = 0
return
end if
i = 1
j = x
do while (i < j)
i = i + 1
j = j / 2
end do
y = i - 1
end function sqrt
end program main1 2
```
program square_root
implicit none
integer :: x, y
x = 4
y = square_root(x)
write (*,*) "The square root of", x, "is", y
x = 8
y = square_root(x)
write (*,*) "The square root of", x, "is", y
contains
function square_root(x) result(y)
implicit none
integer, intent(in) :: x
integer :: y
y = int(sqrt(real(x)))
end function square_root
end program square_root
```
temp.f95:1:2:
1 | ```
| 1
Error: Invalid character in name at (1)
temp.f95:8:20:
8 | y = square_root(x)
| 1
Error: Symbol at (1) is not appropriate for an expression
temp.f95:12:20:
12 | y = square_root(x)
| 1
Error: Symbol at (1) is not appropriate for an expression
temp.f95:17:37:
17 | function square_root(x) result(y)
| 1
Error: PROGRAM attribute of ‘square_root’ conflicts with PROCEDURE attribute at (1)
temp.f95:18:21:
18 | implicit none
| 1
Error: Unexpected IMPLICIT NONE statement in CONTAINS section at (1)
temp.f95:20:32:
20 | integer, intent(in) :: x
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:21:20:
21 | integer :: y
| 1
Error: Unexpected data declaration statement in CONTAINS section at (1)
temp.f95:23:30:
23 | y = int(sqrt(real(x)))
| 1
Error: Unexpected assignment statement in CONTAINS section at (1)
temp.f95:24:7:
24 | end function square_root
| 1
Error: Expecting END PROGRAM statement at (1)
temp.f95:27:2:
27 | ```
| 1
Error: Invalid character in name at (1)
def mySqrt(x):
if x == 0 or x == 1:
return x
start, end, ans = 1, x, 0
while start <= end:
mid = (start + end) // 2
if mid * mid == x:
return mid
if mid * mid < x:
start = mid + 1
ans = mid
else:
end = mid - 1
return ans
The algorithm uses a binary search approach to find the integer square root of the given number x. It starts with the smallest possible answer (1) and the largest possible answer (x), updating the "start" and "end" positions based on whether the current midpoint squared is smaller or larger than x. The integer square root of the number is found when mid * mid == x, or when the closest integer (under or equal to x) value has been located. The binary search approach keeps the time complexity at O(log(x)), making it an efficient solution.
int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int start = 1, end = x, ans;
while (start <= end) {
int mid = (start + end) / 2;
if (mid * mid == x) return mid;
if (mid * mid < x) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
return ans;
}
The algorithm uses a binary search approach to find the integer square root of the given number x. It starts with the smallest possible answer (1) and the largest possible answer (x), updating the "start" and "end" positions based on whether the current midpoint squared is smaller or larger than x. The integer square root of the number is found when mid * mid == x, or when the closest integer (under or equal to x) value has been located. The binary search approach keeps the time complexity at O(log(x)), making it an efficient solution.