【LeetCode】 69. Sqrt(x)

Description

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.

實作 int sqrt(int x)。

計算並回傳 x 的平方根，x是非負整數。

因為回傳的型態是一個整數，小數點之後的部分請全部捨去，只留下並回傳整數部分。

Example:

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.

Solution

• 這題我使用牛頓逼近法去實作。
  • $x_{n+1}=x_n+\frac{f(x)}{f^{\prime }(x)}$
  • 去找
    $f(x)=x^2-a=0$的答案。
• 為了精度問題我使用double去處理。
• 0的時候會出問題，要特別處理。
• 捨去小數點使用floor()即可。

Code

class Solution {
public:
    int mySqrt(int x) {
//      x1 = x0 - f(x)/f'(x)
//      f(x) = x^2 - a = 0
//      x1 = x0 - x^2 - a / 2x
        if(x == 0) return 0;
        
        double a = x, a2 = x;
        do
        {
            a = a2;
            a2 = a - (a * a - x) / (2 * a);
        } while(abs(a - a2) > 0.00001);
        
        return (int)floor(a2);
    }
};

tags: LeetCode C++