Title: Sqrt(x) Source: leetcode.com
Implement int sqrt(int x).
Compute and return the square root of x.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/* https://leetcode.com/problems/sqrtx/ */ class Sqrt { public static void main(String args[]) throws Exception { Sqrt solution = new Sqrt(); System.out.println(solution.mySqrt(2147395599)); } public int mySqrt(int x) throws Exception { if(x==0 || x==1) return x; long lo = 1; long hi = x; while(lo<hi) { long mid = (lo+hi)/2; //System.out.println("lo: "+lo+" mid: "+mid+" hi: "+hi); //Thread.sleep(2000); if(lo==mid) break; if(mid*mid > x) hi = mid; else lo = mid; } return (int)lo; } } |