# \#367 Valid Perfect Square
## *給定一正整數, 判斷此數是否為平方數*
## Log
- build 20210710 by syhuang

## 二分法查找
- binary search實作
- 注意例外(num=1)
- 時間複雜度O(log(n))

 var isPerfectSquare = function(num) {
    if(num==1) return true;
    let left = 0;
    let right = num;
    while(right - left > 1){
        let mid = left + Math.ceil((right-left)/2);
        if(mid*mid == num) return true;//注意overflow
        else if(mid*mid < num) left = mid;
        else right = mid
    }
    return false;
};

## 數學解法
- 平方數必為連續正奇數序列之和(從1開始)
- 時間複雜度為O(sqrt(n))

var isPerfectSquare = function(num) {
    let t = num;
    for(let n=0; t>0; n++){
        t-=(2*n+1);
    }
    return t==0;
};

## 初見
- 將數字質因數分解(sorted),檢查每個質因數是否為偶數個,是的話就是平方數
- leetcode summit timeout QQ

var isPerfectSquare = function(num) {
    var getPrimeFactors = function(val){
        let t = val;
        let result = [];
        for(let candidate=2; t>1; candidate++){
            for(; t%candidate==0; t/=candidate) result.push(candidate);
        }
        return result;
    }
    let PFs = getPrimeFactors(num);//排好序的質因數分解
    let result = true;
    let t = PFs[0];
    let count = 0;
    for(let i=0; i<PFs.length; i++){
        if(t==PFs[i]) count++;
        else{
            if(count%2 != 0){
                result = false;
                break;
            }
            else count=1;
            t = PFs[i];
        }
    }
    if(count%2!=0) result = false;
    return result;
};

## 備註
## 參考
- [參考解](https://leetcode.com/problems/valid-perfect-square/discuss/83874/A-square-number-is-1%2B3%2B5%2B7%2B...-JAVA-code)
###### tags: `leetcode`, `leetcode-easy`