---
# System prepended metadata

title: \#367 Valid Perfect Square
tags: [leetcode, leetcode-easy]

---

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

## 二分法查找
 - binary search實作
 - 注意例外(num=1)
 - 時間複雜度O(log(n))
 ```javascript=
 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))
```javascript=
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
```javascript=
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`