Sqrt(x)

easy

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

x = 4

Expected Output

2

Input

x = 8

Expected Output

2

Explanation: The square root of 8 is 2.828..., and rounding down gives 2.

Constraints

0 <= x <= 2^31 - 1

Hints

Hint 1 — click to reveal

The answer lies somewhere in [0, x] — and that range is sorted with respect to 'is mid*mid <= x'.

Hint 2 — click to reveal

Use long for the multiplication, or compare with division, to avoid 32-bit overflow.

Java Compiler