Check perfect square using binary search

Q: Check perfect square using binary search

This is a Coding & Algorithms interview question from LinkedIn for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Perfect Square Check (Binary Search)

Given a positive integer n, determine whether it is a perfect square (i.e., there exists an integer x such that x*x = n).

Requirements

Do not use built-in square-root functions.
Implement an O(log n) approach.

Input

Integer n ( 1 <= n <= 2^31 - 1 ).

Output

Return true if n is a perfect square, otherwise false .

Examples

n = 16 -> true (4×4)
n = 14 -> false

Notes

Be careful about integer overflow when computing mid * mid .