{x}
blog image

Valid Perfect Square

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

Solution Explanation for Valid Perfect Square

The problem asks to determine if a given positive integer num is a perfect square without using built-in square root functions. Two efficient approaches are presented: Binary Search and a Mathematical approach.

This approach leverages the properties of binary search to efficiently find the square root of num.

Algorithm:

  1. Initialization: Set left boundary l = 1 and right boundary r = num.
  2. Iteration: While l < r, perform a binary search:
    • Calculate the middle value mid = (l + r) / 2 (or using bitwise operation (l + r) >>> 1 for potential efficiency gains).
    • If mid * mid >= num, it means the square root is less than or equal to mid. Update r = mid.
    • Otherwise, the square root is greater than mid. Update l = mid + 1.
  3. Verification: After the loop, l will hold the potential integer square root. Check if l * l == num. If true, num is a perfect square; otherwise, it's not.

Time Complexity: O(log n), where n is the input number. This is because binary search halves the search space in each iteration.

Space Complexity: O(1), as we only use a few variables to store the boundaries and intermediate results.

Solution 2: Mathematical Approach

This method utilizes the mathematical property that the sum of consecutive odd numbers equals a perfect square. The sum of the first n odd numbers is n².

Algorithm:

  1. Initialization: Start with i = 1. This represents the first odd number.
  2. Iteration: Iteratively subtract consecutive odd numbers (i) from num.
  3. Termination: The loop continues until num becomes less than or equal to 0.
  4. Verification: If num is exactly 0 after the loop, it indicates that the original number was a perfect square. Otherwise, it was not.

Time Complexity: O(√n). The loop iterates approximately √n times (number of odd numbers to sum up to n).

Space Complexity: O(1), as we only use a few variables.

Code Examples (Python, Java, C++, Go, TypeScript, Rust)

The code examples for both solutions are provided in the problem description. Each example demonstrates the respective algorithms clearly. Note the use of long or 1LL multiplication in some cases to prevent integer overflow when dealing with large numbers. The Python bisect_left function in Solution 1 provides a concise way to perform the binary search. Go uses sort.Search for a similar efficient implementation.

Choosing the best solution:

The Binary Search approach (Solution 1) is generally preferred because of its guaranteed O(log n) time complexity, which is more efficient than the O(√n) complexity of the mathematical approach (Solution 2), especially for very large input numbers. However, the mathematical approach might be slightly simpler to understand intuitively.