0849HardMathBinary SearchGreedy

Fewest Floor Crates in the Corner Stack

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.

Crates are stacked in the corner of a room, against two walls that meet at a right angle. A crate resting off the floor must be supported: each of the crates directly beneath it, the one behind it, and the one to its side, must be present.

More precisely, a crate at height h above the floor and not touching either wall needs the crate below it, the crate below and one step towards one wall, and the crate below and one step towards the other wall, all present.

A stack of n crates is built. Return the fewest crates that can be touching the floor.

Examples

Example 1

Input: n = 6
Output: 5

Three crates on the floor carry a fourth resting on them, and the two crates still to place each need a fresh floor crate beside them.

Example 2

Input: n = 5
Output: 4

Three crates on the floor carry a fourth, and the fifth needs one more floor crate to rest against.

Example 3

Input: n = 1
Output: 1

A single crate rests on the floor.

Constraints

1 <= n <= 10^9

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 fewest_floor_crates(n: int) -> int:

Java

public int fewestFloorCrates(int n)

The intended approach

Time O(n^(1/3)) since the pile a side-k staircase holds grows as the cube of k.Space O(1).

The densest way to stack crates over a given floor area is a staircase built into the corner: with a floor triangle of side k, the whole pile holds the sum of the triangular numbers up to k, and its floor covers the k-th triangular number. So grow k while the pile that shape holds still fits inside the count, which takes only a few thousand steps because the pile grows as the cube of k. Whatever crates remain are added one at a time along a fresh diagonal, and each new floor crate placed there supports one more level, so the leftovers are covered by adding floor crates until the running capacity reaches them.

Pythonentry point: fewest_floor_crates

def fewest_floor_crates(n):
    # grow a full corner staircase while it still fits
    side = 0
    held = 0
    floor = 0
    while held + (side + 1) * (side + 2) // 2 <= n:
        side += 1
        floor += side                      # the side-th triangular number, built up
        held += side * (side + 1) // 2
    # place the leftovers along a fresh diagonal, one floor crate at a time
    left = n - held
    extra = 0
    supported = 0
    while supported < left:
        extra += 1
        supported += extra
    return floor + extra

The obvious version

Try every floor count upwards and, for each, work out the largest pile it could support by building the tallest staircase that floor allows; report the first floor count whose capacity reaches the crate count. Makes no closed-form argument.

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_fewest_floor_crates(n):
    def capacity(floor):
        # spend the floor crates on the largest complete triangle, then a diagonal
        side = 0
        used = 0
        held = 0
        while used + (side + 1) <= floor:
            side += 1
            used += side
            held += side * (side + 1) // 2
        left = floor - used
        for step in range(1, left + 1):
            held += step
        return held

    floor = 0
    while True:
        floor += 1
        if capacity(floor) >= n:
            return floor

How this problem was checked

Reference solution executed against 12 test cases — 12 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