0242EasyMathBinary SearchNewton's Method

Largest Square Patio

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A landscaper has tiles identical square paving stones on the pallet and wants to lay one solid square patio. Stones are laid whole, never cut, and any stones left over simply stay on the pallet.

Return the side length of the largest square patio that can be laid, counted in stones along one edge. Equivalently, return the largest integer side for which side * side is at most tiles.

Work it out with integer arithmetic: do not call a library square-root routine and do not use an exponentiation operator.

Examples

Example 1

Input: tiles = 27
Output: 5

A patio 5 stones on a side takes 25 stones, so the pallet of 27 covers it and 2 stones stay behind.

Example 2

Input: tiles = 100
Output: 10

A patio 10 stones on a side takes exactly 100 stones, so the pallet is used up and nothing is left over.

Example 3

Input: tiles = 3
Output: 1

A single stone is already a square patio 1 stone on a side, and the other 2 stones stay on the pallet.

Constraints

0 <= tiles <= 2^31 - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def largest_square_side(tiles: int) -> int:

Java

public int largestSquareSide(int tiles)

The intended approach

Time O(log tiles)Space O(1)

The predicate `side * side <= tiles` holds for every side up to the answer and fails for every side beyond it, so the answer is the last side that satisfies it. The code binary searches the range `[0, tiles]` for that boundary, biasing the midpoint upward so the window always shrinks, keeping the midpoint when its square fits and dropping below it when the square overshoots. Only integer multiplication and comparison are used, so nothing is lost to rounding at the top of the range.

Pythonentry point: largest_square_side

def largest_square_side(tiles):
    low = 0
    high = tiles
    while low < high:
        mid = (low + high + 1) // 2
        if mid * mid <= tiles:
            low = mid
        else:
            high = mid - 1
    return low

The obvious version

Grow the side one stone at a time while the next square still fits on the pallet. O(sqrt(tiles)).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_largest_square_side(tiles):
    side = 0
    while (side + 1) * (side + 1) <= tiles:
        side += 1
    return side

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in