easy Valid Perfect Square

Problem Statement

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Examples

- Input: 49
- Expected Output: true
- Justification: (7 * 7) equals 49.
- Input: 55
- Expected Output: false
- Justification: There is no integer whose square is 55.
- Input: 0
- Expected Output: false
- Justification: 0 is not considered a perfect square.

Constraints:

1 <= num <= 2³¹ - 1

Try it yourself

Try solving this question here:

✅ Solution Valid Perfect Square

Problem Statement

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Examples

- Input: 49
- Expected Output: true
- Justification: (7 * 7) equals 49.
- Input: 55
- Expected Output: false
- Justification: There is no integer whose square is 55.
- Input: 0
- Expected Output: false
- Justification: 0 is not considered a perfect square.

Constraints:

1 <= num <= 2³¹ - 1

Solution

Step 1: Start
- Start by checking if the number is less than 2.
Step 2: Binary Search Approach
- Implement a binary search between 2 and the number.
- Calculate the middle and check if its square is equal to the given number.
- If it is equal, return true.
- If it’s less, perform a binary search on the right half.
- If it’s more, perform a binary search on the left half.

Algorithm Walkthrough

Given an input of 49:

Start by checking if 49 is less than 2. It is not, so proceed.
Implement a binary search between 2 and 49.
- Calculate the middle number: ((2 + 49) / 2 = 25)
- (25 * 25) is more than 49, so perform a binary search on the left half (2 to 25).
- New middle: ((2 + 25) / 2 = 13)
- (13 * 13) is more than 49, so perform a binary search on the left half (2 to 13).
- New middle: ((2 + 13) / 2 = 7)
- (7 * 7) equals 49, return true.

Code

java

public class Solution {

  // Function to check whether a given number is a perfect square
  public boolean isPerfectSquare(int num) {
    // if the number is less than 2, check if it is 1
    if (num < 2) return num == 1;

    long left = 2, right = num / 2;
    // Loop until left is less than or equal to right
    while (left <= right) {
      long mid = (left + right) / 2;
      long guess = mid * mid;
      // if guess is equal to num, return true
      if (guess == num) return true;
      // if guess is less than num, update left to mid + 1
      if (guess < num) left = mid + 1;
      // else update right to mid - 1
      else right = mid - 1;
    }
    // if no perfect square is found, return false
    return false;
  }

  // Main method for testing the algorithm with example inputs
  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.isPerfectSquare(49)); // Expected output: true
    System.out.println(solution.isPerfectSquare(55)); // Expected output: false
    System.out.println(solution.isPerfectSquare(0)); // Expected output: false
  }
}

Complexity Analysis

Time Complexity: The time complexity of this algorithm is (O(log n)) because it employs a binary search strategy, effectively halving the search space in each iteration.
Space Complexity: The space complexity is (O(1)), as it uses a constant amount of additional memory space, not dependent on the input size.

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

Stuck on Valid 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 **Valid 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 **Valid 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 **Valid 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 **Valid 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

← Repeated Substring Pattern Move Zeroes →