Valid Perfect Square — Solution in Python, Java & C++
Valid Perfect Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at HCL.
Valid Perfect Square is an easy coding problem on math and binary search, asked in HCL interviews.
- Difficulty: Easy
- Topics: Math, Binary Search
- Asked at: HCL
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer num, return true if it is a perfect square (an integer times itself), without using any built-in sqrt function.
Example 1
Input: num = 16
Output: true
Explanation: 4 × 4 = 16.
Example 2
Input: num = 14
Output: false
Constraints
1 <= num <= 2147483647
Hints for Valid Perfect Square
Hint 1
Binary search k in [1, num] on k*k versus num.
Hint 2
Newton's method converges even faster: k = (k + num/k) / 2.
How to solve Valid Perfect Square
Same monotone answer-space search as integer square root, but the question is exact: does some integer k satisfy k * k == num? Binary search k, comparing without ever forming the product so nothing overflows.
Approach
- Search
kin[1, num]. - For each
mid, compute the quotientq = num / midand remainderr = num % mid. - If
q == midandr == 0, thenmid * mid == numexactly — returntrue. - If
q > mid, thenmidis too small — search higher; otherwise search lower. - An exhausted range means no such integer exists.
Why it works
num / mid compared against mid reproduces the ordering of mid * mid against num without multiplying: quotient greater than mid means the square is short of num, quotient smaller means it overshoots. Equality of the quotient plus a zero remainder is precisely divisibility with matching factors, i.e. an exact square. The comparison is monotone in mid, so binary search applies.
Complexity
- Time —
O(log num) - Space —
O(1)
Pitfalls
mid * midoverflows a 32-bit integer for inputs near 2.1 billion — this is the whole reason for the division form.- The remainder check matters:
num / mid == midalone is true fornum = 8, mid = 2(8 / 2 == 2) even though 8 is not a square. - Built-in
sqrtis disallowed, and floating point is unreliable at this magnitude regardless. - Start the range at
1, not0, so the division is always safe.
Reference solution
Python
def isPerfectSquare(num: int) -> bool:
lo, hi = 1, num
while lo <= hi:
mid = (lo + hi) // 2
sq = mid * mid
if sq == num:
return True
if sq < num:
lo = mid + 1
else:
hi = mid - 1
return FalseJava
public static boolean isPerfectSquare(int num) {
int lo = 1, hi = num;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int q = num / mid;
int r = num % mid;
if (q == mid && r == 0) return true;
if (q > mid) lo = mid + 1;
else hi = mid - 1;
}
return false;
}C++
bool isPerfectSquare(int num) {
int lo = 1, hi = num;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int q = num / mid;
int r = num % mid;
if (q == mid && r == 0) return true;
if (q > mid) lo = mid + 1;
else hi = mid - 1;
}
return false;
}JavaScript
var isPerfectSquare = function(num) {
let lo = 1, hi = num;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
const sq = mid * mid;
if (sq === num) return true;
if (sq < num) lo = mid + 1;
else hi = mid - 1;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search