## 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:

**Brute Force**: Straightforward but inefficient, especially for large values.**Binary Search**: A more efficient approach, significantly faster than brute force.**Newton’s Method**: Even faster, mathematically sophisticated, iterative approach.**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.