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

Contents are not accessible

Contents are not accessible

Contents are not accessible

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

InputOutputExplanation
16True16 is a perfect square because 4 * 4 = 16.
14False14 is not a perfect square because there is no integer whose square is equal to 14.
9True9 is a perfect square because 3 * 3 = 9.

Constraints:

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

Solution

  1. Base Case:
    • If the given number is 0 or 1, return true because 0 and 1 are perfect squares.
  2. 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.
Image

Code

Here is the code for this algorithm:

Python3
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

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible