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.

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= n &lt;= 109


class Solution:
    def minimumBoxes(self, n: int) -> int:
        r = 0
        while (n_upper := r*(r+1)*(r+2)//6) < n:
            r += 1
        m = r*(r+1)//2
        for i in range(r, 0, -1):
            if (n_upper - i) < n:
                break
            n_upper -= i
            m -= 1
        return m
class Solution {

    static final double ONE_THIRD = 1.0d / 3.0d;

    public int minimumBoxes(int n) {
        int k = findLargestTetrahedralNotGreaterThan(n);
        int used = tetrahedral(k);
        int floor = triangular(k);
        int unused = (n - used);
        if (unused == 0) {
            return floor;
        }
        int r = findSmallestTriangularNotLessThan(unused);
        return (floor + r);
    }

    private final int findLargestTetrahedralNotGreaterThan(int te) {
        int a = (int) Math.ceil(Math.pow(product(6, te), ONE_THIRD));
        while (tetrahedral(a) > te) {
            a--;
        }
        return a;
    }

    private final int findSmallestTriangularNotLessThan(int t) {
        int a = -1 + (int) Math.floor(Math.sqrt(product(t, 2)));
        while (triangular(a) < t) {
            a++;
        }
        return a;
    }

    private final int tetrahedral(int a) {
        return (int) ratio(product(a, a + 1, a + 2), 6);
    }

    private final int triangular(int a) {
        return (int) ratio(product(a, a + 1), 2);
    }

    private final long product(long... vals) {
        long product = 1L;
        for (long val : vals) {
            product *= val;
        }
        return product;
    }

    private final long ratio(long a, long b) {
        return (a / b);
    }

}
class Solution {
public:
    int minimumBoxes(int n) {
        
        // Find the biggest perfect pyramid
        uint32_t h = cbrt((long)6*n);
        uint32_t pyramid_box_num = h*(h+1)/2*(h+2)/3;   // /6 is split to /2 and /3 to avoid long to save space
        if ( pyramid_box_num > n ){
            h--;
            pyramid_box_num = h*(h+1)/2*(h+2)/3;            // /6 is split to /2 and /3 to avoid long to save space
        }
        
        // Calculate how many floor-touching boxes in the pyramid
        int pyramid_base_num = (h)*(h+1)/2;
        
        // Get the number of boxes to be added to the perfect pyramid
        n -= pyramid_box_num;
        
        // Find how many floor-touching boxes are added
        int z = sqrt(2*n);
        int max_box_added = z*(z+1)/2;
        if ( max_box_added < n)
            z++;
        
        return pyramid_base_num+z;
    }
};
var minimumBoxes = function(n) {
    //Binary search for the height of the biggest triangle I can create with n cubes available.
    let lo=1,hi=n,result
    let totalCubes=x=>x*(x+1)*(x+2)/6 //the total cubes of a triangle with height x 
    while(lo+1<hi){
        let mid=lo+hi>>1
        if(totalCubes(mid)<=n)
            lo=mid
        else 
            hi=mid
    }
	let f=(x)=>Math.floor(Math.sqrt(2*x)+1/2)// the i-th element of the sequence 1,2,2,3,3,3,4,4,4,4,5,...
    result=(lo)*(lo+1)/2// the base of the largest complete triangle 1+2+3+..+H
    n-=totalCubes(lo) //remove the cubes of the complete triangle
    return result+f(n)  // the base of the largest+ the extra floor cubes
};
Building Boxes