Valid Perfect Square

You can check if a number is a perfect square by using a binary search method or trying successive integers. Here, I will explain the binary search method, as it is more efficient.

Initialize Two Pointers: Set two pointers, left and right, to 1 and the given number, respectively.
Binary Search: Perform a binary search by repeatedly dividing the search interval in half:
- Compute the midpoint, mid, of the current search interval.
- Check if mid * mid equals the given number. If so, return true.
- If mid * mid is less than the given number, update left to mid + 1.
- If mid * mid is greater than the given number, update right to mid - 1.
Result: If the search ends without finding a perfect square, return false.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num

        while left <= right:
            mid = (left + right) // 2
            square = mid * mid
            
            if square == num:
                return True
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1

        return False

The time complexity of this solution is (O(\log n)), where (n) is the given number, and the space complexity is (O(1)), as we are using a constant amount of extra space.

Identifying Problem Isomorphism

“Valid Perfect Square” has an approximate mapping to “Guess Number Higher or Lower”.

In “Valid Perfect Square”, you are given a positive integer num and you need to check whether it is a perfect square or not. This is typically solved by applying binary search algorithm between 1 and num. We iteratively calculate the square of mid-value, and if it equals num, then num is a perfect square. If it’s less, we move our search to the upper half, otherwise to the lower half.

“Guess Number Higher or Lower” is where we are playing the Guess game. You are guessing a number between 1 and n. Each time you guess the wrong number, you get a hint whether the number is higher or lower. You use binary search to optimize your guessing strategy.

Both problems involve binary search as the main mechanism to solve them, making them approximate isomorphic problems. The concept of binary search can be mapped from one problem to the other.

“Guess Number Higher or Lower” is simpler. It just requires implementing a binary search, while “Valid Perfect Square” requires extra steps of squaring the mid-value and handling the edge cases carefully to avoid arithmetic overflow.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num

        while left <= right:
            mid = (left + right) // 2
            if mid * mid == num:
                return True
            elif mid * mid < num:
                left = mid + 1
            else:
                right = mid - 1

        return False

Problem Classification

Based on the terminology used in the problem statement, this problem can be classified as:

Number Theory: The problem is about perfect squares, which are numbers that can be expressed as the square of some other number. This falls under the study of number theory.
Binary Search: Although not explicitly mentioned in the problem statement, one of the optimal ways to solve this problem without using a built-in library function like sqrt, is using a binary search approach. This would classify the problem in the category of binary search problems.
Decision Problem: The problem is a decision problem as it requires a yes or no answer - the number is either a perfect square (return true) or not a perfect square (return false).

Language Agnostic Coding Drills

Understanding Binary Search: Binary search is a search algorithm used to find the position of a target value within a sorted array. It compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until it is successful or the remaining half is empty.
Implementing Basic Binary Search: The first drill is to implement a simple binary search on a sorted array. This teaches the basic mechanics of binary search like how to calculate mid, and how to adjust the search space.
Applying Binary Search to Problem-Specific Context: Once we have a basic binary search, we need to adjust it to fit our specific problem context. In this case, instead of searching for a specific number in a sorted array, we are trying to find a number such that when it is multiplied by itself it equals the given number. This is a form of binary search where the condition is not just equality but a specific operation on the mid value.
Handling Edge Cases and Finalizing the Code: The last step involves handling edge cases like negative numbers, or large numbers that could potentially cause overflow, and then integrating all the parts into a final, polished solution.

Problem Solving Approach:

Start with the number itself and 1 as the range for binary search.
Calculate the mid of the range, and square it.
If the square of mid is equal to the number, return true indicating that the number is a perfect square.
If the square of mid is less than the number, that means the potential square root lies in the right half of the range, so adjust the left boundary to mid + 1.
If the square of mid is more than the number, that means the potential square root lies in the left half of the range, so adjust the right boundary to mid - 1.
Repeat the above steps until left is greater than right. If we haven’t found a number that squares to the given number, return false, indicating that the number is not a perfect square.

Targeted Drills in Python

Understanding Binary Search

A simple implementation of binary search can be done with the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def binary_search(array, target):
    left = 0
    right = len(array) - 1

    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Implementing Basic Binary Search

To practice binary search, one could define an array and a target number, and then use the function defined above:

1
2
3
array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
print(binary_search(array, target))  # it should return 5 which is the index of number 6

Applying Binary Search to Problem-Specific Context

We can modify the binary search algorithm to suit our current problem. Instead of searching for a specific number in an array, we will adjust the condition to check if the square of mid equals num.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def is_perfect_square(num):
    left, right = 1, num
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == num:
            return True
        elif mid * mid < num:
            left = mid + 1
        else:
            right = mid - 1
    return False

print(is_perfect_square(16))  # it should return True
print(is_perfect_square(14))  # it should return False

Handling Edge Cases and Finalizing the Code

The previous function already considers edge cases because it iteratively reduces the search space until it is empty. It is also prepared for large numbers as it uses a binary search approach, significantly reducing the time complexity.

This way, each piece has been coded and tested individually. All the drills combined make up the final solution to the problem.