Valid Perfect Square

Problem Statement

Given a positive integer num, the task is to determine whether or not this number is a perfect square. A number is considered a perfect square if there exists some integer n such that n * n = num. This problem requires a solution without using advanced mathematical functions like square root (sqrt), provided by built-in libraries. The challenge is to check for the perfect square nature using possibly simpler algorithms or iterative approaches.

Examples

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

Approach and Intuition

To solve the problem of determining if a number is a perfect square, without using built-in functions like sqrt, a basic method is required that checks each number sequentially or uses a more efficient algorithm like binary search. Below is an intuitive breakdown and approach using a simple algorithm:

1. Initialize a variable i starting from 1 and increment it in each step.
2. In each iteration, calculate i * i.
   • If i * i equals num, then num is a perfect square, and return true.
   • If i * i becomes greater than num, then no integer n can satisfy n * n = num (since squares grow quickly), and return false.
   • Continue the iteration until i * i exceeds num.
3. This approach works efficiently for smaller numbers, but for very large numbers close to 2^31 - 1, this method can be slow.
4. An optimization can be achieved using a binary search approach on i from 1 to num, reducing the number of comparisons significantly.
   • Set low to 1 and high to num.
   • While low is less than or equal to high, compute the middle point mid.
   • If mid * mid equals num, return true.
   • If mid * mid is less than num, set low to mid + 1.
   • Otherwise, set high to mid - 1.

These steps ensure that the number is checked against all possible square roots in an optimal manner, provided the constraints.

Solutions

class Solution {
  public boolean checkPerfectSquare(int number) {
    if (number < 2) return true;
    
    long mid = number / 2;
    while (mid * mid > number) {
      mid = (mid + number / mid) / 2;
    }
    return (mid * mid == number);
  }
}