Problem

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.

Examples

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Solution

Method 1 - Using Multiplication

public boolean isPerfectSquare(int num) {
	for (int i = 1; i*i <= num; i++) {
		if (i*i == num) {
			return num;
		}
	}
	return false;
}

Complexity

  • ⏰ Time complexity: O(sqrt (n))
  • 🧺 Space complexity: O(1)

Method 2 - Using Binary Search

public boolean isPerfectSquare(int num) {
	if (num < 4) {
		return num == 1;
	}
	int lo = 1;
	int hi = num / 2;
	while (lo <= hi) {
		long mid = lo + (hi - lo) / 2;
		long midSq = (long) mid * mid; // Might overflow. num = 808021.
		if (midSq == num) {
			return true;
		} else if (midSq > num) {
			hi = (int) mid - 1;
		} else {
			lo = (int) mid + 1;
		}
	}
	return false;
}

Complexity

  • ⏰ Time complexity: O(log (n))
  • 🧺 Space complexity: O(1)

Note that asymptotically O(sqrt n) is worse then O (lg n). For eg. sqrt(1024) = 32; log (1024) = 10