"""
Exercise 2: Sqrt(x) (LeetCode 69)

Return floor(sqrt(x)) for a non-negative integer x WITHOUT math.sqrt or **.
Binary search the answer: the largest m with m * m <= x.
"""

def my_sqrt(x):
    # TODO
    return 0


# --- self-check: do not modify below this line ---
cases = [(4, 2), (8, 2), (0, 0), (1, 1), (2147395599, 46339), (99, 9)]
ok = True
for x, want in cases:
    got = my_sqrt(x)
    print(x, "->", got)
    ok = ok and got == want
print("PASS" if ok else "FAIL")