Sqrt(x)
Easy · Binary Search · Math · Binary Search
Problem
Given a non-negative integer x, return the square root of x rounded down: the largest integer r with r * r <= x.
Do not use a built-in power or square-root function or operator (no pow(x, 0.5), x ** 0.5 or math.sqrt). Work with whole numbers only.
Examples
Input: x = 15 Output: 3
3 * 3 = 9 fits under 15, but 4 * 4 = 16 does not.
Input: x = 36 Output: 6
36 is 6 * 6 exactly.
Input: x = 0 Output: 0
The square root of 0 is 0.
Constraints
- 0 <= x <= 2^31 - 1
Approaches
- Baseline: count up from zero — time O(√x), space O(1)
Follow-up
Newton's method, r = (r + x // r) // 2 from r = x, also reaches the answer and needs only about log log x rounds once it is close. The first use case below asks for a cube root, where the same binary search works with mid ** 3.
Related problems
Start free on Cariara · Coding problems · System design studio
