algoadvance

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

• 1 <= num <= 2^31 - 1

Clarifying Questions

1. Q: Should the function handle inputs less than 1? A: No, based on the constraints, num will always be 1 or greater.

2. Q: Can we use libraries like math.sqrt for this problem? A: You should avoid using the sqrt function directly to showcase algorithmic thinking.

3. Q: How should the function behave if num is 1? A: Since 1 is a perfect square (1 * 1 = 1), the function should return True for an input of 1.

Strategy

We can determine if a number is a perfect square by leveraging a binary search algorithm. Here’s the step-by-step strategy:

1. Binary Search Initialization: Initialize two pointers, left starting at 1 and right starting at num.
2. Binary Search Loop:
   • Calculate mid as the average of left and right.
   • Compute the square of mid.
   • If mid * mid equals num, return True.
   • If mid * mid is less than num, move the left pointer to mid + 1.
   • If mid * mid is greater than num, move the right pointer to mid - 1.
3. Termination: If the loop ends without finding a perfect square, return False.

Code

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

Time Complexity

• Binary Search Complexity: The binary search approach works in O(log num) time complexity because we halve the search space with each step.

This optimized solution ensures that we can efficiently determine if the given number is a perfect square or not.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?