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 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
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.
What it practices
- Binary search on the answer
- Search the space of candidate answers when feasibility is monotonic.
Related katas
- Cutting Ribbons Medium Free The longest equal piece length that still yields k pieces.
- Koko Eating Bananas Medium Free The slowest eating speed that still finishes every pile in time.
- Minimum Days to Make Bouquets Medium Free Earliest day enough adjacent flowers have bloomed for all the bouquets.
- Ship Packages Within D Days Medium Free Smallest ship capacity that delivers the conveyor belt on schedule.