Sqrt

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:

  1. public class Solution {
  2.   public int mySqrt(int x) {
  3.     int lo = 1, hi = x;
  5.     while (lo < hi) {
  6.       int mid = lo + (hi - lo) / 2;
  8.       if (mid < x / mid) {
  9.         lo = mid + 1;
  10.       } else {
  11.         hi = mid;
  12.       }
  13.     }
  15.     return (lo == x / lo) ? lo : lo - 1;
  16.   }
  17. }