Minimize the Floor Footprint of Supported Boxes

### Problem Place `n` unit cubes in a cubic room whose width, length, and height are all n. Cubes may be placed on the floor. If a cube sits on another cube, every vertical side of the lower supporting cube must touch a wall or another cube. Return the smallest possible number of cubes touching the floor. ```cpp class Solution { public: int minimumBoxes(int n); }; ``` ### Examples **Example 1:** ```text n = 5 Output: 4 Explanation: A complete corner arrangement with three floor cubes supports four total cubes; one more floor cube permits a fifth. ``` **Example 2:** ```text n = 7 Output: 5 Explanation: Five floor cubes in a corner staircase can support seven total cubes; four floor cubes support at most five. ``` ### Constraints - `1 <= n <= 10^9`. ### Clarifying Questions The support condition applies to all four vertical sides of a cube that has another cube above it. Room side length and the number of cubes are both n in the source. ```hint Inspect the structure Which cube's four vertical sides must be supported when another cube rests above it? ``` ### Reasoning checkpoints - Show that a claimed arrangement meets every supporting cube's four-side rule. - Prove that no arrangement with a smaller floor footprint can hold all `n` cubes, using arithmetic valid up to `10^9`. ### Optional extensions How could binary search replace either incremental loop over layer counts?