Question

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

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

Constraints:

1 <= num <= 2³¹ - 1

Algorithm

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

Code

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;
    }

}

############

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;
        while (left < right) {
            long mid = (left + right) >>> 1;
            if (mid * mid >= num) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left * left == num;
    }
}

// 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:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left < right:
            mid = (left + right) >> 1
            if mid * mid >= num:
                right = mid
            else:
                left = mid + 1
        return left * left == 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

func isPerfectSquare(num int) bool {
	left, right := 1, num
	for left < right {
		mid := (left + right) >> 1
		if mid*mid >= num {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left*left == num
}

function isPerfectSquare(num: number): boolean {
    let left = 1;
    let right = num >> 1;
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (mid * mid < num) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left * left === num;
}

use std::cmp::Ordering;
impl Solution {
    pub fn is_perfect_square(num: i32) -> bool {
        let num: i64 = num as i64;
        let mut left = 1;
        let mut right = num >> 1;
        while left < right {
            let mid = left + (right - left) / 2;
            match (mid * mid).cmp(&num) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid - 1,
                Ordering::Equal => return true,
            }
        }
        left * left == num
    }
}

367 - Valid Perfect Square

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions