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:

🎯 STRICT STANDOUT — Valid Perfect Square — problem

1. Why / judgment

Membership test in the set of squares. Brute multiply every k until k²≥num is O(√num). Binary search on the integer root domain [1..num] (or tighter [1..min(num,2^16)] for 32-bit) is the interview default when sqrt is banned. Overflow on mid*mid is the silent bug — use division compare or 64-bit.

2. Big-O derivation (K11)

BS: O(log num) multiplications.
Newton integer iteration also O(log num) typically faster constants.
Linear scan k=1,2,... while k*k≤num: O(√num) — OK for tiny num, fails large 2^31-1 under tight limits.
Space O(1).

3. Pattern + when-NOT (K12)

Name: BINARY SEARCH ON INTEGER ROOT

Recognition: “is perfect square?”, no floating sqrt, positive integer domain.

When-NOT: Allowed math.sqrt + epsilon → not this constraint set. Need exact integer sqrt value → same BS but return mid when equal (see Sqrt page). Need sum of squares / Lagrange → different number theory.

4. Edge hand-run (K13)

num=1 → true (1²).
num=49 → true; 55 → false.
constraints usually 1≤num; if 0 appears treat per spec (page example false).
overflow: mid near 2^31 → mid*mid must not wrap in 32-bit.

5. Interviewer follow-ups (model answers)

Q1. Why not float sqrt then cast?
A: Floating error near large integers can misclassify; interview often bans lib sqrt explicitly.

Q2. Upper bound for lo/hi?
A: hi=num works; for num≥4, hi=num//2 is safe optimization since (num//2)² ≥ num for those.

Q3. Newton vs binary search?
A: Both fine; Newton needs careful integer termination to avoid oscillation.

6. Short drills

Drill: hand BS for 16 → true; 14 → false.
Drill: name the overflow fix (1LL*mid*mid or num/mid >= mid).

✅ 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.

🎯 STRICT STANDOUT — Solution Valid Perfect Square

1. Why / judgment

Maintain lo/hi on candidate roots. Compare mid² to num: equal → true; mid² < num → search right; else left. Correctness: squares are strictly increasing on positive integers, so the search space is totally ordered — one of the cleanest binary-search-on-answer instances.

2. Big-O derivation (K11)

Each iteration O(1); iterations O(log num) ⇒ O(log num) time, O(1) space.
Trace 49: mids 25→13→7 → 7*7=49 true.
Trace 55: converges with no mid²=55 → false.
Trace 1: special-case or BS finds 1.

3. Pattern + when-NOT (K12)

Name: BINARY SEARCH ON ANSWER (MONOTONE PREDICATE mid² ? num)

Recognition: integer domain search for exact square root existence.

When-NOT: Need floor(sqrt) for other uses (bucket sizes) → return hi after BS for largest mid with mid²≤num. Need floating approximation → Newton on reals, different API.

4. Edge hand-run (K13)

num=1 → true.
num=2 → false.
num=2147395600 = 46340² → true (classic LC edge).
num=2147483647 → false, no overflow crash if compare safe.

5. Interviewer follow-ups (model answers)

Q1. Infinite loop risk?
A: Use while lo≤hi with hi=mid−1 / lo=mid+1, or while lo<hi with a clear terminal assignment. Trace n=2 and n=3.

Q2. Why mid*mid can be wrong in C++ int?
A: 46341² overflows 32-bit signed; use long long or division.

Q3. Is O(√n) ever preferred?
A: Only tiny constraints or when you also need all factors; interviews expect log for this prompt.

6. Short drills

Drill: implement with compare num/mid >= mid avoiding overflow.
Drill: return false for non-square near INT_MAX.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 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 →