Knowledge Guide
Home › DSA › Recursion

Solution Perfect Square

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:

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
Image

Code

Here is the code for this algorithm:

java
public class Solution {

  public static boolean isPerfectSquare(int num) {
    return isPerfectSquareHelper(num, 0, num);
  }

  private static boolean isPerfectSquareHelper(int num, int low, int high) {
    if (low > high) {
      return false;
    }

    int mid = low + (high - low) / 2;

    if ((long) mid * mid == num) {
      return true;
    } else if ((long) mid * mid > num) {
      return isPerfectSquareHelper(num, low, mid - 1);
    } else {
      return isPerfectSquareHelper(num, mid + 1, high);
    }
  }

  public static void main(String[] args) {
    int[] examples = { 16, 14, 9 };

    for (int num : examples) {
      boolean isPerfect = isPerfectSquare(num);
      System.out.println(num + " is a perfect square: " + isPerfect);
    }
  }
}

Time and Space Complexity

The time complexity of the algorithm is because we perform a binary search on the possible square roots.

The space complexity of the algorithm is due to the recursion stack used in the binary search process.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Perfect Square? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Perfect Square** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Perfect Square** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Perfect Square**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Perfect Square**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Check PrimeSolution Number Frequency →