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

• Java
• C++
• Python

• 
  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