69. Sqrt(x) #

Problem #

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Problem Summary #

Implement the int sqrt(int x) function. Compute and return the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is kept, and the decimal part will be truncated.

Solution Approach #

• The problem asks us to find the square root of x

• According to the problem statement, the value range of the square root of x must be within [0,x]. The values in this interval are increasing and ordered, bounded, and can be accessed by index. Satisfying these three points also exactly satisfies the three major conditions for binary search. So solution approach one is binary search.

• Solution approach two is Newton’s method. Finding the square root of x means finding all solutions that satisfy the equation x^2 - n = 0.

  

Code #

package leetcode

// Solution 1: Binary search, find the last integer n that satisfies n^2 <= x
func mySqrt(x int) int {
	l, r := 0, x
	for l < r {
		mid := (l + r + 1) / 2
		if mid*mid > x {
			r = mid - 1
		} else {
			l = mid
		}
	}
	return l
}

// Solution 2: Newton's method https://en.wikipedia.org/wiki/Integer_square_root
func mySqrt1(x int) int {
	r := x
	for r*r > x {
		r = (r + x/r) / 2
	}
	return r
}

// Solution 3: The Quake III game engine has an implementation 4 times faster than STL's sqrt https://en.wikipedia.org/wiki/Fast_inverse_square_root
// float Q_rsqrt( float number )
// {
// 	long i;
// 	float x2, y;
// 	const float threehalfs = 1.5F;

// 	x2 = number * 0.5F;
// 	y  = number;
// 	i  = * ( long * ) &y;                       // evil floating point bit level hacking
// 	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
// 	y  = * ( float * ) &i;
// 	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
// //	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
// 	return y;
// }