Coding questions · LinkedIn

Check perfect square using binary search

This question evaluates a candidate's competency in implementing binary search and handling integer arithmetic and overflow considerations when checking numeric properties. Commonly asked to assess algorithmic complexity analysis and practical coding ability within the Coding & Algorithms domain, it emphasizes practical application and O(log n) performance rather than purely conceptual reasoning.

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.

Perfect Square Check

Return whether n is a perfect square using binary search without sqrt.

Hints

Choose a representation that makes the core operation simple.
Handle empty and boundary inputs before the main algorithm.