Show problems as
Classic problem #1739HardMathBinary SearchGreedy

Building Boxes

Real-world version: Fewest Floor Crates in the Corner Stack
Tracked in this browser only
Read Building Boxes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_floor_crates(n: int) -> int:
Java
public int fewestFloorCrates(int n)

More on the same topics