Number Theory · 161Easy
Sqrt(x)
Given a non-negative integer x, return the square root of x rounded DOWN to the nearest integer. You may not use any built-in exponent or square root function.
Constraints
- 0 <= x <= 2^31 - 1
Examples
mySqrt(4) -> 2 mySqrt(8) -> 2 // 2.828... truncated mySqrt(0) -> 0 mySqrt(1) -> 1 mySqrt(2) -> 1 // 1.414... truncated mySqrt(2147395600) -> 46340 // a perfect square near the upper bound
Edge cases
- x = 0 and x = 1 return themselves.
- The result is TRUNCATED, never rounded up.
Show the target complexity (spoiler)
- Naive
- O(sqrt(x)) time — increment a counter until its square exceeds x.
- Target
- O(log x) time — binary search over [0, x] for the largest integer whose square does not exceed x. (Newton's method converges even faster.)
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/22-number-theory/161-sqrtx.js ./practice c 161