Reference: LeetCode EPI 11.4
Difficulty: Easy

Problem

Given a positive integer num, write a function which returns True if num is a perfect square else False.

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

Example: 

1

Follow up:

Analysis

Brute-Force & Cheating

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// brute-force
public boolean isPerfectSquare(int num) {
  for (int i = 1; i <= num; ++i) {
    if (i * i == num) {
      return true;
    }
  }
  return false;
}

// cheating
public boolean isPerfectSquare(int num) {
  int x = (int) Math.sqrt(num);
  return x * x == num;
}

Time: $O(N)$ for brute-force.
Space: $O(1)$

Standard Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isPerfectSquare(int num) {
  int lo = 1, hi = num;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (mid * mid == num) {
      return true;
    }
    if (mid > num / mid) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return false;
}

Other Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isPerfectSquare(int num) {
  int lo = 1, hi = num;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (mid >= num / mid) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  // check
  return (lo * lo == num);
}

Time: $O(\log{N})$
Space: $O(1)$