Question

Formatted question description: https://leetcode.ca/all/367.html

 367	Valid Perfect Square

 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:

 Input: 16
 Returns: True

 Example 2:

 Input: 14
 Returns: False

Algorithm

Search from 1 to sqrt(num) to see if there is a number whose square is exactly equal to num.

Code

Java

public class Valid_Perfect_Square {


    public boolean isPerfectSquare(int num) {
        if (num == 0 || num == 1) {
            return true;
        }

        int l = 1, h = num;

        // binary search for mid*mid
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (mid == num / mid && num % mid == 0) {
                return true;
            }
            else if (mid < num / mid) {
                l = mid + 1;
            }
            else {
                h = mid - 1;
            }
        }

//        int[] array = IntStream.rangeClosed(Integer.MIN_VALUE, Integer.MAX_VALUE).toArray();
//        Arrays.binarySearch(array, num);

        return false;
    }

}

All Problems

All Solutions