# 【LeetCode】 367. Valid Perfect Square

## Description
> Given a positive integer num, write a function which returns True if num is a perfect square else False.

> Note: Do not use any built-in library function such as `sqrt`.

> 給予正整數 num ，寫一個函式回傳 num 是否為完美平方數。

> 提示：不要使用任何內建函式庫的函式，例如`sqrt`。

## Example:

Example 1:

Input: 16
Output: true


Example 2:

Input: 14
Output: false

## Solution

* 既然不能使用內建的`sqrt`，那就自己實作一個就好了。
* [這邊](https://hackmd.io/@Zero871015/LeetCode-69)有實作`sqrt`的方法。
* 實作完成之後，就做開根號再平方看看有沒有一樣即可。

### 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);
    }
    
    bool isPerfectSquare(int num) {
        int temp = mySqrt(num);
        return temp * temp == num;
    }
};

###### tags: `LeetCode` `C++`