Skip to main content

367. Valid Perfect Square

easy

Decide whether a positive integer is a perfect square — without sqrt(). Tests binary-search-on-answer and the Newton's-method shortcut, both of which avoid floating-point precision issues.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a positive integer num, return true if num is a perfect square or false otherwise. A perfect square is an integer that is the product of some integer with itself. You must not use any built-in library function, such as sqrt.

Constraints

  • 1 <= num <= 2^31 - 1

Examples

Example 1

Input
num = 16
Output
true

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

Example 2

Input
num = 14
Output
false

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Binary search the integer x in [1, num] such that x * x == num. Beware of overflow when num is near 2^31 - 1 — use 64-bit arithmetic or compare x against num / x.

Hint 2

Newton's method: x_{k+1} = (x_k + num / x_k) / 2 converges quadratically. Stop when x*x <= num and (x+1)*(x+1) > num.

Hint 3

Math identity: the sum of the first k odd integers equals k^2. Subtract 1, 3, 5, 7, ... from num; if you hit 0, num is a perfect square.

Hint 4

The odd-sum approach is O(sqrt(num)) and uses pure integer arithmetic — clean but slower than binary search for large inputs.

Solution approach

Reveal approach

Binary search lo=1, hi=num. While lo <= hi: mid = lo + (hi - lo) / 2. Compute mid * mid in 64-bit (or compare mid against num / mid to avoid overflow). If equal, return true. If less, lo = mid + 1; else hi = mid - 1. Return false on loop exit. O(log num) time, O(1) space. Newton's-method variant: start x = num; while x * x > num set x = (x + num / x) / 2; finally check x * x == num. Both run in microseconds even for num near 2^31 - 1. The odd-sum identity (1+3+5+...+(2k-1) = k^2) gives a clean O(sqrt(num)) approach with no overflow risk.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

More Math practice problems

See all Math problems →