Square root, rounded down
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.
- Input
x = 30- Output
5
5 * 5 = 25 is not more than 30, and 6 * 6 = 36 is.
- Input
x = 49- Output
7
49 is a perfect square.
- 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
- Microsoft, SDE intern on-campus interview, 2023 (GeeksforGeeks)
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.
