Leetcode – Valid Perfect Square Solution in Python

Spread the love

Introduction

In this article, we will discuss the Valid Perfect Square problem, and explore various methods to solve it using Python. The problem can be found at LeetCode under the title “Valid Perfect Square” and belongs to the category of algorithm problems.

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.

Analyzing the Problem

A perfect square is a number that can be expressed as the square of an integer. For example, 16 is a perfect square because it can be written as 4^2. In this problem, you are required to determine if a given positive integer is a perfect square without using the built-in sqrt function or similar library functions.

Let’s look into different approaches to solve this problem:

Approach 1: Brute Force

The most naive approach would be to iterate through all the numbers from 1 to num and check if the square of the current number is equal to num. If we find such a number, then num is a perfect square.

def isPerfectSquare(num: int) -> bool:
    i = 1
    while i * i <= num:
        if i * i == num:
            return True
        i += 1
    return False

This approach, however, is not efficient especially for large values of num as its time complexity is O(sqrt(n)).

Approach 2: Binary Search

An optimization over the brute-force approach can be achieved by using a binary search algorithm. The idea is to search for the square root of num in a range from 1 to num by repeatedly dividing the search interval in half.

def isPerfectSquare(num: int) -> bool:
    if num < 2:
        return True
    
    left, right = 2, num // 2
    while left <= right:
        mid = left + (right - left) // 2
        guess = mid * mid
        if guess == num:
            return True
        elif guess > num:
            right = mid - 1
        else:
            left = mid + 1
            
    return False

This approach has a time complexity of O(log n) which is significantly better than the brute-force approach for large values of num.

Approach 3: Newton’s Method

Newton’s method can also be used to find if a number is a perfect square. Newton’s method is an iterative method to approximate the root of a real-valued function. In this context, we can use it to approximate the square root of num.

def isPerfectSquare(num: int) -> bool:
    if num < 2:
        return True
    
    x = num // 2
    while x * x > num:
        x = (x + num // x) // 2
        
    return x * x == num

This approach converges much faster and has a complexity of O(log(log n)).

Approach 4: Math Trick (1 + 3 + 5 + … + (2n-1) = n^2)

There is a mathematical trick that can solve this problem in constant time. The sum of the first n odd numbers is equal to n^2. This means if num can be represented as a sum of a series of odd numbers starting from 1, it must be a perfect square.

def isPerfectSquare(num: int) -> bool:
    i = 1
    while num > 0:
        num -= i
        i += 2
    return num == 0

This approach has a complexity of O(sqrt(n)), but with very small constant factors, making it faster in practice compared to the brute force approach.

Wrapping Up

In this article, we have discussed four different approaches to solving the Valid Perfect Square problem on LeetCode using Python. Here is a summary:

  1. Brute Force: Straightforward but inefficient, especially for large values.
  2. Binary Search: A more efficient approach, significantly faster than brute force.
  3. Newton’s Method: Even faster, mathematically sophisticated, iterative approach.
  4. Math Trick: Exploits the sum of odd numbers to solve the problem with low constant factors.

Choosing the best approach depends on the specific requirements and constraints of your application. In general, for a coding interview, it’s good to know and understand different approaches, as this demonstrates your problem-solving skills and knowledge of algorithms.

Leave a Reply