Valid Perfect Square

Given a positive integer num, return true if it is a perfect square, that is, the square of some integer, and false otherwise. Do not use built-in functions such as Math.sqrt. This is LeetCode 367.

Example 1
Input: num = 16
Output: true
Explanation: 4 × 4 = 16.
Example 2
Input: num = 14
Output: false
Explanation: 3 × 3 = 9 and 4 × 4 = 16, so no integer squares to 14.

How to Think About It

Step 1: Look for an exact value

The question is whether some integer r between 1 and num has r × r == num. Squares grow as r grows, so the squares 1, 4, 9, 16, 25, ... are a sorted list, and searching a sorted list for an exact value is ordinary binary search.

Step 2: Compare the square of the middle

  • If mid × mid == num: it is a perfect square.
  • If mid × mid < num: the root, if there is one, is bigger: lo = mid + 1.
  • If mid × mid > num: it is smaller: hi = mid - 1.
  • If the range becomes empty, no integer squares to num.

Step 3: Use long for the square

num can be up to 231 - 1, so mid can start around 1 billion, and mid × mid overflows an int. Keeping the variables as long makes every square exact.

Walkthrough

num = 14:

lohimidmid × midDecision
114749too big, hi = 6
1639too small, lo = 4
46525too big, hi = 4
44416too big, hi = 3

The range is empty: 14 lies between 3 × 3 and 4 × 4, so it is not a perfect square.

Java Solution

This is the exact-match template, searching for a number whose square equals num.

Java
public class ValidPerfectSquare {

    public static boolean isPerfectSquare(int num) {
        long lo = 1;
        long hi = num;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long square = mid * mid;       // long, so the square cannot overflow
            if (square == num) {
                return true;
            } else if (square < num) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;                      // no integer squares to num
    }

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(16));           // true
        System.out.println(isPerfectSquare(14));           // false
        System.out.println(isPerfectSquare(2147483647));   // false
    }
}

The original implementation, ValidPerfectSquare.java, is on GitHub. A neat alternative uses the fact that perfect squares are sums of odd numbers (1 = 1, 4 = 1 + 3, 9 = 1 + 3 + 5, ...): subtract 1, 3, 5, ... from num until it reaches 0 or goes negative. That takes O(√n) steps, slower than binary search.

Complexity

  • Time: O(log n).
  • Space: O(1).