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;
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/valid-perfect-square/
    // Time: O(sqrt(num))
    // Space: O(1)
    class Solution {
    public:
        bool isPerfectSquare(int num) {
            long i = 0;
            while (i * i < num) ++i;
            return i * i == num;
        }
    };
    
  • class Solution(object):
      def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        r = num
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        r = (r + num / r) / 2
        return r * r == num
    
    

All Problems

All Solutions