Solution: Perfect Square

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Perfect Square

Table of Contents

Contents are not accessible

Problem Statement

Write a Recursive Solution to Check if a Given Number is a Perfect Square or Not.

The problem is to determine whether a given positive number is a perfect square or not. A square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.

Examples

Input	Output	Explanation
16	True	16 is a perfect square because 4 * 4 = 16.
14	False	14 is not a perfect square because there is no integer whose square is equal to 14.
9	True	9 is a perfect square because 3 * 3 = 9.

Constraints:

1 <= n <= 10<sup>4</sup>

Solution

Base Case:
- If the given number is 0 or 1, return true because 0 and 1 are perfect squares.
Recursive Case:
- The algorithm performs a binary search to find the square root of the number and check if it is a perfect square.
- Calculate the mid value between a lower bound and an upper bound.
- Check if the square of the mid value is equal to the given number.
  - If it is equal, return true because the number is a perfect square.
  - If it is less than the given number, make a recursive call with an updated lower bound of mid + 1.
  - If it is greater than the given number, make a recursive call with an updated upper bound of mid - 1.
- Repeat the process until a perfect square is found or the lower bound becomes greater than the upper bound.

Code

Here is the code for this algorithm:

Python3

. . . .

Time and Space Complexity

The time complexity of the algorithm is $O(log N)$ because we perform a binary search on the possible square roots.

The space complexity of the algorithm is $O(log N)$ due to the recursion stack used in the binary search process.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible