Skip to content
Katabench
Try free

Integer Square Root

Easy About 10 min Free, no account needed

Floor of the square root, found without floating point.

The brief

Given a non-negative long n, return the floor of its square root, the largest r with r * r <= n. No floating-point shortcuts: Math.Sqrt loses precision near 10^18, so do it with integers.

The performance bar

The obvious approach counts up from zero until the square exceeds n, fine for small inputs, but the hidden test uses n near 10^18, where the answer is around a billion steps away, so the linear count is far too slow. You will need a method that homes in on r in far fewer than a billion steps.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the largest r with r * r <= n.
    public long Isqrt(long n)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Binary search on the answer
Search the space of candidate answers when feasibility is monotonic.

Related katas