Exit
  1. Learn
  2. Check
  3. Solve
  4. Reflect

The answers themselves are sorted

The whole square root of n is the largest r whose square is at most n. There is no list to search, but the possible answers 0, 1, 2, 3 and so on are in order. "Is r squared more than n?" goes no, no, no, then yes forever.

A question that flips once is all halving needs. Find the first r whose square passes n, then step back one.

The first too-big r: then step back one, and that is the answer.
Root of 40: which r is the first with r × r > 40?
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
lowhigh

Try 5: 5 × 5 = 25 is not more than 40. The first too-big r is later: low = 6.

Move 1 of 5

Pick a range that surely holds the answer

Here n is at most 10 to the power 15, and 32,000,000 times 32,000,000 is already more than that. So the first too-big r lies somewhere from 0 to 32,000,000.

Search that range with the same loop as before. Where it looked at a list entry, use the middle times itself.

0 to 32,000,000: covers every possible answer.
Use a long: in C++ and Java. The middle times itself can be far bigger than an int holds.
In code
answers = []
for n in nums:
    low, high = 0, 32_000_000
    while low < high:
        mid = (low + high) // 2
        if mid * mid > n:
            high = mid
        else:
            low = mid + 1
    answers.append(low - 1)
return answers