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