How do you approach Sqrt(x)?

Binary search is a great approach here.

What is the time complexity of Sqrt(x)?

Time complexity: O(log x) - binary search. Space complexity: O(1) - constant space.

What are common mistakes on Sqrt(x)?

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

Sqrt(x)

EasyAlgorithms

Description

Given a non-negative integer `x`, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator (such as `Math.sqrt` or `**` or `x ** 0.5`).

Example 1

Input: x = 4

Output: 2

Explanation: The square root of 4 is 2.

Example 2

Input: x = 8

Output: 2

Explanation: The square root of 8 is 2.828..., rounded down to 2.

Constraints

- 0 <= x <= 2^31 - 1

Sqrt(x): approach, complexity and pitfalls

An easy binary search problem, graded against 8 test cases (5 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

Binary search is a great approach here.
Search in the range [0, x] for the largest integer whose square is <= x.
Be careful with integer overflow when computing mid * mid.

The optimal approach

Show the approach: Binary Search

Use binary search in the range [0, x]. For each midpoint, check if mid * mid <= x. Track the largest valid mid as the answer.

If mid * mid equals x, return mid. If mid * mid < x, search the right half. If mid * mid > x, search the left half.

Time: O(log x) - binary search
Space: O(1) - constant space

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

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

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

Sqrt(x)

EasyAlgorithms

Description

Example 1

Input: x = 4

Output: 2

Explanation: The square root of 4 is 2.

Example 2

Input: x = 8

Output: 2

Explanation: The square root of 8 is 2.828..., rounded down to 2.

Constraints

- 0 <= x <= 2^31 - 1

Sqrt(x): approach, complexity and pitfalls

An easy binary search problem, graded against 8 test cases (5 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

Binary search is a great approach here.
Search in the range [0, x] for the largest integer whose square is <= x.
Be careful with integer overflow when computing mid * mid.

The optimal approach

Show the approach: Binary Search

Use binary search in the range [0, x]. For each midpoint, check if mid * mid <= x. Track the largest valid mid as the answer.

If mid * mid equals x, return mid. If mid * mid < x, search the right half. If mid * mid > x, search the left half.

Time: O(log x) - binary search
Space: O(1) - constant space

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

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

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.