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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Valid Perfect Square and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →