Wednesday, January 7, 2015

Sqrt(x) (LeetCode Math)

Question: Implement int sqrt(int x). Compute and return the square root of x.

Idea: Binary search. Let low variable start from 0, high variable start from x, test ((low+high)/2 )* ((low+high)/2). If smaller than x, increase low, otherwise decrease high.

Time: O(lgx) Space: O(1)

Code:
 public class Solution {  
   public int sqrt(int x) {  
     long low=0;  
     long high=x;  
     while(low<=high)  
     {  
       long mid=(high+low)/2;  
       if(mid*mid==x)  
         return (int)mid;  
       if(mid*mid<x)  
         low=mid+1;  
       else  
         high=mid-1;  
     }  
     return (int)high;  
   }  
 }  

No comments:

Post a Comment