Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

C++:
01 int sqrt(int x) {
02     if(x<=0)
03         return 0;
04     int y=1;
05     int min=1;
06     int max=x;
07     while(true){
08         int z=x/y;
09         if(y==z)
10             return y;
11         if((y>z)&&(y<max))
12              max=y;
13         if((y<z)&&(y>min))
14              min=y;
15         if((y%2)&&(z%2))
16              y=y/2+z/2+1;
17         else
18              y=y/2+z/2;
19         if(y<=min)
20              return min;
21         if(y>=max)
22              return max1;
23     }
24 }
Alternatively, we can do binary search.

C++:
01 int sqrt(int x) {
02     if(x<=0)
03        return 0;
04     int s=1;
05     int b=x;
06     while(s<=b){
07          int mid=(s+b)/2;
08          if(mid==x/mid);
09              return mid;
10          if(mid>x/mid)
11               b=mid1;
12          else
13               s=mid+1;
14     }
15     return b;
16  }
Advertisements
This entry was posted in Binary search, Number trick. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s