Formatted question description: https://leetcode.ca/all/1739.html

# 1739. Building Boxes

## Level

Hard

## Description

You have a cubic storeroom where the width, length, and height of the room are all equal to `n`

units. You are asked to place `n`

boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:

- You can place the boxes anywhere on the floor.
- If box
`x`

is placed on top of the box`y`

, then each side of the four vertical sides of the box`y`

**must**either be adjacent to another box or to a wall.

Given an integer `n`

, return *the minimum possible number of boxes touching the floor*.

**Example 1:**

**Input:** n = 3

**Output:** 3

**Explanation:** The figure above is for the placement of the three boxes.

These boxes are placed in the corner of the room, where the corner is on the left side.

**Example 2:**

**Input:** n = 4

**Output:** 3

**Explanation:** The figure above is for the placement of the four boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

**Example 3:**

**Input:** n = 10

**Output:** 6

**Explanation:** The figure above is for the placement of the ten boxes.

These boxes are placed in the corner of the room, where the corner is on the back side.

**Constraints:**

`1 <= n <= 10^9`

## Solution

The ideal situation is that the `i`

-th level from the top (where `i`

starts from 1) contains `i * (i + 1) / 2`

boxes. Calculate the minimum number of boxes under the ideal situation such that the number of boxes is at least `n`

. After that, calculate the remaining boxes at the bottom level where the number of boxes is exactly `n`

. Let `remain`

be the number of remaining boxes. Find the minimum possible value `min`

such that `min * (min + 1) / 2 >= remain`

. Let `currLevel`

be the number of boxes in the last level just above the bottom level. The result is `currLevel + min`

.

```
class Solution {
public int minimumBoxes(int n) {
if (n <= 3)
return n;
int total = 0;
int levelCount = 0;
int currLevel = 0;
while (total < n) {
levelCount++;
currLevel += levelCount;
total += currLevel;
}
if (total == n)
return currLevel;
total -= currLevel;
currLevel -= levelCount;
int remain = n - total;
int increase = findMin(remain);
return currLevel + increase;
}
public int findMin(int remain) {
int min = (int) Math.sqrt(remain * 2);
while (min * (min + 1) / 2 < remain)
min++;
return min;
}
}
```