384. Whole Square Root
A tile layer wants to cover a square floor whose side is a whole number of tiles. She has exactly x square tiles and may leave some unused, but every tile she lays must be part of one complete square.
Return the largest whole number s such that s * s <= x, the side of the biggest square she can finish. You may not use any built-in square-root or power function, and you should not use floating-point arithmetic. Aim for O(log x) time. Remember that s * s can overflow a 32-bit integer for large x.
Example 1
- Input:
- x = 17
- Output:
- 4
- Explanation:
4 * 4 = 16 fits in 17 tiles, but 5 * 5 = 25 does not.
Example 2
- Input:
- x = 36
- Output:
- 6
- Explanation:
36 tiles make a perfect 6 by 6 square.
Constraints
0 ≤ x ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log x)
- Space
- O(1)