Welcome to Subscribe On Youtube

367. Valid Perfect Square

Description

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 <= 231 - 1

Solutions

Solution 1: Binary search

Solution 2: Math trick

This is a math problem:

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
so 1+3+...+(2n-1) = (2n-1 + 1)n/2 =
  • 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;
        }
    }
    
  • class Solution {
    public:
        bool 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;
        }
    };
    
  • 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
    
    
  • 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
        }
    }
    
    

All Problems

All Solutions