# [LeetCode] Sqrt(x) (Java)

Implement int sqrt(int x).

Compute and return the square root of x.

## Analysis

We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type.

There is another way, which is Newton’s Method. You can check the code here.

## Complexity

The complexity is O(log x).