# Valid Perfect Square
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-perfect-square)
Canonical: https://scaleengineer.com/dsa/problems/valid-perfect-square
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
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`

# Approaches
## Brute Force: Linear Search
This approach iterates through numbers from 1 up to `num` and checks if the square of any number `i` equals `num`. To optimize, we only need to iterate as long as `i * i <= num`.
**Time:** O(sqrt(n)), where n is the input number `num`. In the worst case, we iterate from 1 up to `sqrt(num)`. · **Space:** O(1), as we only use a constant amount of extra space for the loop variable.
**Pros:** Simple to understand and implement.; Requires minimal memory.
**Cons:** Inefficient for large input numbers.; May result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The most straightforward method is to check every integer `i` starting from 1 to see if its square is equal to the given number `num`.

We can start a loop with a counter `i` (as a `long` to prevent overflow when squaring) from 1.

In each iteration, we calculate the square of `i`.
- If `i * i` equals `num`, we have found an integer whose square is `num`, so `num` is a perfect square, and we can return `true`.
- If `i * i` exceeds `num`, it means that the square of `i` and any subsequent integer will also be greater than `num`. Therefore, `num` cannot be a perfect square, and we can stop the search and return `false`.

This method is simple but can be slow for very large values of `num`.

```java
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) return false;
        if (num == 1) return true;
        
        for (long i = 1; i * i <= num; i++) {
            if (i * i == num) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize a `long` variable `i` to 1.
- Loop as long as the square of `i` is less than or equal to `num`.
- Inside the loop, check if `i * i` is equal to `num`.
- If it is, return `true`.
- If the loop finishes without finding such an `i`, it means `num` is not a perfect square, so return `false`.

## Binary Search
A more efficient approach is to use binary search. Since the square roots of numbers are monotonically increasing, we can search for an integer `x` in the range `[1, num]` such that `x * x = num`.
**Time:** O(log n), where n is the input number `num`. The search space is halved in each iteration. · **Space:** O(1), as we only use a few variables to keep track of the search range.
**Pros:** Significantly faster than linear search for large numbers.; Guaranteed to find the solution without hitting time limits.
**Cons:** Slightly more complex to conceptualize and implement than the brute-force approach.
### Explanation
We are looking for an integer `x` where `x * x = num`. The possible values for `x` lie in a sorted range from 1 to `num`. This makes binary search an ideal candidate for finding `x` efficiently.

We define a search space with `left = 1` and `right = num`.

We then repeatedly check the middle element `mid` of the current search space:
- We calculate `square = mid * mid`. To avoid potential integer overflow, `mid` and `square` should be of type `long`.
- If `square` is equal to `num`, we've found the integer square root, and we return `true`.
- If `square` is less than `num`, it means the actual square root must be larger than `mid`. So, we discard the left half of the search space by setting `left = mid + 1`.
- If `square` is greater than `num`, the square root must be smaller than `mid`. We discard the right half by setting `right = mid - 1`.

This process continues until `left` becomes greater than `right`. If the loop terminates without finding a perfect square, we return `false`.

```java
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) return false;
        if (num == 1) return true;
        
        long left = 1;
        long right = num;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}
```
### Algorithm
- Initialize `left = 1` and `right = num`.
- Loop while `left` is less than or equal to `right`.
- Calculate `mid = left + (right - left) / 2`. Use `long` to avoid overflow.
- Calculate `square = mid * mid`.
- If `square == num`, return `true`.
- If `square < num`, update `left = mid + 1`.
- If `square > num`, update `right = mid - 1`.
- If the loop ends, return `false`.

## Mathematical Approach: Newton's Method
Newton's method is a fast numerical technique for finding the root of a function. We can use it to find the square root of `num` by finding the root of the function `f(x) = x^2 - num`.
**Time:** O(log n). The convergence is quadratic, meaning the number of correct digits roughly doubles with each iteration. It's generally faster than binary search. · **Space:** O(1), as it only requires a single variable for the iteration.
**Pros:** Extremely fast convergence.; Elegant mathematical solution.
**Cons:** The underlying mathematical concept might be less familiar than binary search.; Requires careful handling of integer division and potential edge cases.
### Explanation
Newton's method is an iterative algorithm that produces successively better approximations of the roots of a function. To find `sqrt(num)`, we seek the root of `f(x) = x^2 - num`.

The iteration formula is `x_{k+1} = x_k - f(x_k) / f'(x_k)`. For our function, this simplifies to `x_{k+1} = (x_k + num / x_k) / 2`.

We can start with an initial guess, for instance, `x = num`. We then repeatedly apply the update rule. The sequence of `x` values converges very quickly to the actual square root of `num`.

The loop continues as long as our guess `x` squared is greater than `num`. Once the loop terminates, `x` will be the integer part of the square root.

Finally, we check if `x * x` is exactly equal to `num` to confirm if it's a perfect square.

```java
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) return false;
        long x = num;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }
        return x * x == num;
    }
}
```
### Algorithm
- Initialize a `long` variable `x` with the value of `num` as an initial guess.
- Loop as long as `x * x` is greater than `num`.
- Inside the loop, update `x` using the formula: `x = (x + num / x) / 2`.
- After the loop terminates, `x` holds the integer floor of the square root of `num`.
- Return `true` if `x * x == num`, and `false` otherwise.

# Solutions
### Java

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

### CPP

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

### Python

```python
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
```