Log inSign up
easyleetcodeNot Started

Valid Perfect Square

Given a positive integer num, return true if num is a perfect square or false otherwise without using built-in sqrt functions.

Binary Search
Solve on leetcode
Lesson

Problem Statement

Given a positive integer num, return true if num is a perfect square or false otherwise.\n\nA perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.\n\nYou must not use any built-in library function, such as sqrt.

Example 1 · Example 1: Valid Square:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2 · Example 2: Invalid Square:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

Constraints:

  • 1 <= num <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply binary search to verify exact mathematical properties.
  • Manage arithmetic overflow in numerical search algorithms.
  • Understand alternative mathematical identities (sum of first n odd numbers).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determine if num is a perfect square without sqrt().
  • Monotonic search space [1, num].

Algorithmic Decision Tree:

  • low = 1, high = num.
  • While low <= high: mid = low + (high - low) / 2.
  • If mid * mid == num -> return true.
  • If mid * mid < num -> low = mid + 1.
  • Else -> high = mid - 1.
  • Return false.

Connected Patterns:

Sqrt(x)Sum of Square NumbersBinary Search

1. Linear Increment Check

Intuition

Loop i from 1 upwards. If i * i == num return true; if i * i > num return false.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Loop i = 1 while (long)i * i <= num.
  2. Step 2: If i * i == num return true.
  3. Step 3: Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isPerfectSquare(int num) {
10 long long i = 1;
11 while (i * i <= num) {
12 if (i * i == num) return true;
13 i++;
14 }
15 return false;
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(sqrt(n)) — Loop runs sqrt(num) times.
  • Space complexity: O(1) — O(1) auxiliary space.

2. Odd Number Subtraction Property

Intuition

A square of n is the sum of the first n odd numbers: 1 + 3 + 5 + ... + (2n-1) = n2. Subtract 1, 3, 5... from num. If num reaches exactly 0, it is a perfect square.

When to apply: Math trivia / elegant alternative.

Algorithm

  1. Step 1: Set odd = 1.
  2. Step 2: While num > 0: num -= odd, odd += 2.
  3. Step 3: Return num == 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isPerfectSquare(int num) {
10 long long odd = 1;
11 while (num > 0) {
12 num -= odd;
13 odd += 2;
14 }
15 return num == 0;
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(sqrt(n)) — Takes sqrt(num) subtraction steps.
  • Space complexity: O(1) — O(1) auxiliary memory.

3. Binary Search on Range [1, num]

Intuition

Initialize low = 1, high = num. While low <= high, compute mid. If (long)mid * mid == num, return true. If mid * mid < num, low = mid + 1; else high = mid - 1. Return false if not found.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: Initialize low = 1, high = num.
  2. Step 2: While low <= high:
  3. - mid = low + (high - low) / 2.
  4. - sq = (long)mid * mid.
  5. - If sq == num return true.
  6. - If sq < num low = mid + 1, else high = mid - 1.
  7. Step 3: Return false.

Trace for num = 16

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Initial range: low=1, high=16
Visual state
Values and pointers at this exact step
pointers
S
1
16
64
256
0
↑ low
1
↑ low
2
↑ mid
3
↑ high
Check / comparison
8 * 8 = 64 > 16 -> Search left half.
Decision / next transition
Set high = 7.
Why this step matters

Initial range: low=1, high=16. mid=8. 82 = 64 > 16. Search left: high = mid - 1 = 7.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isPerfectSquare(int num) {
10 long long low = 1, high = num;
11 while (low <= high) {
12 long long mid = low + (high - low) / 2;
13 long long sq = mid * mid;
14 if (sq == num) return true;
15 if (sq < num) low = mid + 1;
16 else high = mid - 1;
17 }
18 return false;
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(log n) — Halves search interval each step in at most 31 iterations.
  • Space complexity: O(1) — Requires O(1) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Increment CheckO(sqrt(n))O(1)Check i * i sequentially.Linear stepping.
2.Odd Number SubtractionO(sqrt(n))O(1)Subtract consecutive odd numbers.Repeated subtraction.
3.Binary SearchOptimalO(log n)O(1)Binary search on candidate domain [1, num].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • num = 1 -> returns true (1 * 1 = 1).
  • num = 2, 3 -> returns false.
  • num = 231 - 1 -> prevent integer overflow.
  • Largest perfect square in 32-bit int: 463402 = 2147395600 -> returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Discuss integer overflow upfront (cast mid to 64-bit integer before multiplying).
  2. Mention the mathematical property 1 + 3 + 5 + ... + (2k - 1) = k2 as an interesting alternative.
  3. Explain why binary search is O(log n) compared to linear O(sqrt n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the mathematical relation between odd numbers and perfect squares?

Back to DSA Sheet