Valid Perfect Square

Difficulty: Easy | Acceptance: 44.90% | Paid: No Topics: Math, Binary Search

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.

• Examples
• Constraints
• Approach 1: Linear Search
• Approach 2: Binary Search
• Approach 3: Newton’s Method
• Approach 4: Bit Manipulation (Sum of Odd Numbers)

Examples

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4² = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742² = 14 and 3.742 is not an integer.

Constraints

1 <= num <= 2³¹ - 1

Approach 1: Linear Search

Intuition We can iterate through integers starting from 1 and check if the square of the current integer equals the input number. If the square exceeds the number, we know it is not a perfect square.

Steps

• Initialize a variable i to 1.
• Loop while i * i is less than or equal to num.
• If i * i equals num, return true.
• If i * i exceeds num, return false.
• Increment i in each iteration.

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

Complexity

• Time: O(√n) — In the worst case, we iterate up to the square root of n.
• Space: O(1) — We only use a single variable for iteration.
• Notes: Simple to implement but inefficient for very large numbers compared to binary search.

Approach 2: Binary Search

Intuition Since the squares of integers are sorted (1, 4, 9, 16…), we can use binary search to efficiently find if num exists in this sequence of squares without calculating them all.

Steps

• Initialize left to 1 and right to num.
• While left is less than or equal to right:
  • Calculate mid using left + (right - left) / 2 to avoid overflow.
  • Calculate square = mid * mid.
  • If square equals num, return true.
  • If square is less than num, move left to mid + 1.
  • If square is greater than num, move right to mid - 1.
• If the loop finishes, return false.

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

Complexity

• Time: O(log n) — We halve the search space in each iteration.
• Space: O(1) — Constant space for pointers.
• Notes: Much faster than linear search for large inputs. Care must be taken with integer overflow in languages like Java and C++ when calculating mid * mid.

Approach 3: Newton’s Method

Intuition Newton’s Method (also known as the Newton-Raphson method) is an efficient root-finding algorithm. We can use it to approximate the square root of num by iteratively improving our guess.

Steps

• Start with an initial guess x equal to num.
• While x * x is greater than num:
  • Update x to be the average of x and num / x (i.e., x = (x + num / x) / 2).
• Once the loop terminates, check if x * x equals num.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 1:
            return False
        x = num
        while x * x > num:
            x = (x + num // x) // 2
        return x * x == num

Complexity

• Time: O(log n) — Converges quadratically, which is very fast.
• Space: O(1) — Uses a single variable.
• Notes: This is often the fastest practical method for finding square roots, though it involves division which can be slightly slower than bit operations.

Approach 4: Bit Manipulation (Sum of Odd Numbers)

Intuition A perfect square n² can be represented as the sum of the first n odd numbers. 1² = 1 2² = 1 + 3 3² = 1 + 3 + 5 … We can subtract consecutive odd numbers from num. If we reach exactly 0, it is a perfect square.

Steps

• Initialize a variable subtractor to 1.
• While num is greater than 0:
  • Subtract subtractor from num.
  • Increment subtractor by 2 (to get the next odd number).
• If num becomes 0, return true.
• If num becomes negative, return false.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 1:
            return False
        i = 1
        while num > 0:
            num -= i
            i += 2
        return num == 0

Complexity

• Time: O(√n) — We perform roughly √n subtractions.
• Space: O(1) — Constant space.
• Notes: This is a clever mathematical trick that avoids multiplication and division, though it has the same time complexity as linear search.