Integer Square Root

Problem

Return the integer square root of a non-negative integer n: the largest integer x with x * x <= n.

Use Newton's iteration x = (x + n // x) // 2 starting from n, which converges in O(log n) steps. Return n unchanged for 0 and 1.

Hint

Newton's method halves the error each round, so the loop stops quickly.

case 1

in: [0]

expected: 0

case 2

in: [1]

expected: 1

case 3

in: [4]

expected: 2

case 4

in: [8]

expected: 2

case 5

in: [16]

expected: 4

case 6

in: [1000000]

expected: 1000

Starter codePython

def integer_sqrt(n):
    # Your code here
    pass

6 test cases · run your code against them in the editor