367. Valid Perfect Square

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.

Follow up: Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

• 1 <= num <= 2^31 - 1

Tags

Math, Binary Search

Solution

Perform Binary Search in the interval [2, num/2]. Note that it is always true if num < 2.

Complexity

• Time complexity: $O(\log(n))$

• Space complexity: $O(1)$

Code

 func isPerfectSquare(num int) bool {
	if num < 2 {
		return true
	}
	for l, r := 2, num/2; l <= r; {
		mid := l + (r-l)/2
		square := mid * mid
		if square == num {
			return true
		}
		if square > num {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return false
}

Reference

1. 有效的完全平方数