Problem Statement

Given a positive integer num, determine if it is a perfect square.

Return true if num is a perfect square, otherwise return false. You cannot use built-in square root functions.

Example 1:

Input: num = 16
Output: true
Explanation: 16 = 4 * 4

Example 2:

Input: num = 14
Output: false
Explanation: 14 is not a perfect square

Constraints:

• 1 ≤ num ≤ 2³¹ – 1

---

Approach to Solve the Problem (Simple Language)

Idea:

• A perfect square is a number that can be expressed as x * x for some integer x.
• To check if num is a perfect square, we can use binary search instead of iterating all numbers.

Steps:

1. Initialize left = 1 and right = num.
2. While left <= right:
   • Calculate mid = left + (right - left) / 2.
   • If mid * mid == num, return true.
   • If mid * mid < num, move left = mid + 1.
   • If mid * mid > num, move right = mid - 1.
3. If no mid satisfies mid * mid == num, return false.

Why binary search works:

• Perfect squares increase monotonically.
• x*x grows faster than x, so binary search efficiently finds the square root.

Important Note:

• Use long for multiplication (mid * mid) to avoid integer overflow for large num.

---

Java Code Solution (Binary Search)

public class ValidPerfectSquare {

    public static boolean isPerfectSquare(int num) {
        if (num < 2) return true; // 1 and 0 are perfect squares

        long left = 1, right = num;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;

            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int num = 16;
        boolean result = isPerfectSquare(num);
        System.out.println(num + " is perfect square? " + result); // Output: true
    }
}

---

Dry Run Example

Input:

num = 16

Step-by-step Execution:

1. Initialize: left = 1, right = 16
2. Iteration 1:
   • mid = 1 + (16-1)/2 = 8
   • mid*mid = 64 > 16 → move right = 7
3. Iteration 2:
   • mid = 1 + (7-1)/2 = 4
   • mid*mid = 16 == 16 → return true

Result: true → 16 is a perfect square.

---

Textual Diagram for Understanding

num = 16
Binary search range: [1,16]

Step 1: mid=8 -> 8*8=64 -> >16 -> move right=7
Step 2: mid=4 -> 4*4=16 -> ==16 -> found perfect square

Return true

---

Complexity Analysis

• Time Complexity: O(log num)
  • Binary search halves the search space each time.
• Space Complexity: O(1)
  • Only a few variables used, no extra data structures.