How do you approach Valid Perfect Square?

Squares are monotonically increasing, so binary search the candidate root between 1 and num.

What is the time complexity of Valid Perfect Square?

Time complexity: O(log n). Space complexity: O(1).

What are common mistakes on Valid Perfect Square?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Valid Perfect Square

EasyAlgorithms

Description

Given a positive integer `num`, return `true` if it is a perfect square - that is, if it is the square of some integer. Do **not** use any built-in square-root function.

Example 1

Input: num = 16

Output: true

Example 2

Input: num = 14

Output: false

Example 3

Input: num = 1

Output: true

Constraints

- 1 <= num <= 2^31 - 1 - Built-in sqrt is not allowed. - Aim for O(log n).

Valid Perfect Square: approach, complexity and pitfalls

An easy binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Squares are monotonically increasing, so binary search the candidate root between 1 and num.
Compare mid * mid against num and narrow accordingly.
In fixed-width languages mid * mid overflows - compare with mid <= num / mid instead, or use a wider type.

The optimal approach

Show the approach: Binary search the root

Squaring is monotonic over the positive integers, so the candidate roots form a sorted space even though nothing was handed to you as an array. Binary search `1..num`, compare `mid * mid` to the target, and narrow.

The practical hazard is overflow. With `num` up to 2^31 - 1, `mid` can approach 46341, and `mid * mid` exceeds 32-bit range in languages with fixed-width ints. The standard defences are comparing via division (`mid <= num / mid`) or widening the type. JavaScript's doubles and Python's arbitrary-precision ints avoid it, but this is the detail interviewers ask about, so it is worth naming aloud.

A tighter upper bound helps: no root exceeds `num / 2` for `num > 4`, which trims an iteration or two.

The elegant alternative is worth knowing: every perfect square is a sum of consecutive odd numbers (1, 1+3, 1+3+5, ...), so subtracting successive odds from `num` and checking for exactly zero is an O(sqrt n) solution with no multiplication at all. Newton's method converges even faster. Binary search remains the expected answer because it generalizes.

Time: O(log n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

← Back to problems

Valid Perfect Square

EasyAlgorithms

Description

Given a positive integer `num`, return `true` if it is a perfect square - that is, if it is the square of some integer. Do **not** use any built-in square-root function.

Example 1

Input: num = 16

Output: true

Example 2

Input: num = 14

Output: false

Example 3

Input: num = 1

Output: true

Constraints

- 1 <= num <= 2^31 - 1 - Built-in sqrt is not allowed. - Aim for O(log n).

Valid Perfect Square: approach, complexity and pitfalls

An easy binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Squares are monotonically increasing, so binary search the candidate root between 1 and num.
Compare mid * mid against num and narrow accordingly.
In fixed-width languages mid * mid overflows - compare with mid <= num / mid instead, or use a wider type.

The optimal approach

Show the approach: Binary search the root

A tighter upper bound helps: no root exceeds `num / 2` for `num > 4`, which trims an iteration or two.

Time: O(log n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.