Challenge: Integer Square Root

Lab Python Intermediate 20 points

Read n and print the largest whole number r with r × r ≤ n. Use binary search on the answer – no math.sqrt, no ** 0.5.

Input

One whole number n (0 ≤ n ≤ 10¹⁸).

Output

The integer square root.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

The answer is between 0 and n.

If mid * mid <= n, the answer is at least mid; otherwise it's below mid.

Use mid = (lo + hi + 1) // 2 so the loop always makes progress.

Solution explanation

Even for n = 10¹⁸ this takes about 60 steps.

Show solution

n = int(input())
lo, hi = 0, n
while lo < hi:
    mid = (lo + hi + 1) // 2
    if mid * mid <= n:
        lo = mid
    else:
        hi = mid - 1
print(lo)

Output

Answer