Binary Search Searching the answer

240. Sqrt(x)

You are given a list of non-negative integers xs. For each value x in it, find its square root rounded down: the largest whole number r with r · r ≤ x. Return these roots in the same order as xs.

For example, the square root of 8 is about 2.83, so its root rounded down is 2. A perfect square such as 25 gives its exact root, 5.

Do not use a built-in square root or power function, such as sqrt or pow. An interviewer will ask you to calculate the root yourself.

Example 1

Input: xs = [8, 25, 26, 99]

Output: [2,5,5,9]

Explanation: 2 · 2 = 4 fits under 8 and 3 · 3 = 9 does not, so 8 gets 2. 25 = 5 · 5 gets 5, and so does 26, because 6 · 6 = 36 is too big. For 99, 9 · 9 = 81 fits and 10 · 10 = 100 does not.

Example 2

Input: xs = [0, 1, 2, 3, 4]

Output: [0,1,1,1,2]

Explanation: 0 and 1 are their own square roots. 2 and 3 round down to 1, and 4 = 2 · 2.

Example 3

Input: xs = [1000000000000, 999999999999]

Output: [1000000,999999]

Explanation: 10¹² is 1,000,000 · 1,000,000, so its root is exactly 1,000,000. One less is no longer a perfect square, and its root drops to 999,999.

Check your understanding

Work out the answer for this input before you write any code.

xs = [15, 16, 17]

Constraints

1 ≤ xs.length ≤ 10⁵
0 ≤ xs[i] ≤ 9 × 10¹⁵

Clarifying questions

What you would ask an interviewer before writing any code.