69. Sqrt(x)

Implement int sqrt(int x).

Return the floor if x is not a perfect square.

Approach :  Using binary search making sure that overflow does not happen by taking long long.

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

class Solution { public: int mySqrt(int x) { if(x <= 1){ return x; } int low = 0, high = x / 2; //long to prevent overflow long long mid; while(low <= high){ mid = (low + high) / 2; //needs to be long to prevent overflow long long t = mid * mid; //second part is to return floor if x is not perfect square if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){ break; } else if(x < t){ high = mid - 1; }else{ low = mid + 1; } } return mid; } };

Here is the link to the ideone solution : http://ideone.com/taTCKu