InternDoor

Square root, rounded down

Easybinary search · math

Reported in interviews at (where)

Given a whole number x, return the biggest whole number whose square is not more than x: the square root of x rounded down.

Do it without a built-in square root or power function. Watch out: squaring a number near x can overflow a 32-bit int.

Example 1
Input
x = 30
Output
5

5 * 5 = 25 is not more than 30, and 6 * 6 = 36 is.

Example 2
Input
x = 49
Output
7

49 is a perfect square.

Example 3
Input
x = 0
Output
0

The root of 0 is 0.

Limits

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

Hints

Hint 1

The answer lies between 0 and x: binary search on it.

Hint 2

Compare mid with x / mid instead of mid * mid with x, or use a 64-bit square.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.