# LeetCode Easy 367. Valid Perfect Square

tags: leetcode

問題

• Explore
• Problems

アイデア

与えられた正整数numが平方数か調べます．sqrtは使ってはいけないようです．

大きい数の平方数は大きくなるという単調性を活かして二分探索が出来ると考えられます．

解法

探索する範囲の左端を1として右端をnumとします．

そして，その間の値midの二乗がnumと一致するかどうかに応じて条件分岐をします．

気を付けるのはoverflowです．C++ではlongを使えば大丈夫です．

計算量

• 時間計算量
  • $O(\log num)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  bool isPerfectSquare(int num) {
    long left = 1, right = num;
    while (left < right) {
      long mid = left + (right - left) / 2;
      if (num < mid * mid)
        right = mid - 1;
      else if (num == mid * mid)
        return true;
      else
        left = mid + 1;
    }
    return false;
  }
};