Similar Problems

Similar Problems not available

Valid Perfect Square - Leetcode Solution

Companies:

LeetCode:  Valid Perfect Square Leetcode Solution

Difficulty: Easy

Topics: math binary-search  

Problem Statement:

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 Output: true

Example 2:

Input: 14 Output: false

Solution:

Approach:

  • If the given number is 1, return True.
  • Start with 2 as the potential square root of the given number and loop through until the square of the current number is greater than or equal to the given number.
  • Check if the square of the current number is equal to the given number or not. If it is, return True. If not, return False.

Code:

def isPerfectSquare(num): if num == 1: return True

currentNum = 2

while currentNum * currentNum <= num:
    if currentNum * currentNum == num:
        return True
    currentNum += 1
    
return False

Time Complexity:

The time complexity of this approach is O(sqrt(n)) as we are looping through from 2 until the square of the current number is greater or equal to the given number.

Space Complexity:

The space complexity of this approach is O(1) as we are not using any extra data structures to store the input.

Valid Perfect Square Solution Code

1