Building Boxes

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:

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:


Solution:

First, we try some examples:

1 box -> 
4 boxes -> 1 + (1 + 2)
10 boxes -> 1 + (1 + 2) + (1 + 2 + 3)

...


n boxes -> 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + ... + ?

If n could write in such form:

cur = 1 + (1 + 2) + ... + (1 + 2 + ... + j)

Then, it is clear that the minimum possible number of boxes touching the floor is (1 + 2 + ... + j)

So, let's try to find the maximum j that cur < n:

int cur = 0, i = 0, j = 0;
while(cur < n) {
    ++j;
    i += j;
    cur += i;
}


If cur equals n, then just return i.

Then we try to build boxes like this:



cur = 1 + 3 + 6 ... + i + (1 + 2 + 3 + ... + j)


We now try to find min j that cur >= n.


while(cur < n) {
	++j;
	cur += j;
}


For example:


If n = 14


We first find that 10 = 1 + (1 + 2) + (1 + 2 + 3)


Then we try to find min j that 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + ... + j) >= n, like the way we build in picture above.


In this case, 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3) = 16 >= 14 = n, so j is 3


Then the final result is i+j



class Solution {
    public int minimumBoxes(int n) {
        int total = 0, floor = 0, bound = 0;
        while (total < n) {
            bound ++;
            floor += bound;
            total += floor;
        }
        if (total == n) return floor;
        total -= floor;
        floor -= bound;
        bound = 0;
        while (total < n) {
            bound ++;
            total += bound;
        }
        return floor + bound;
    }
}