<p>You have a cubic storeroom where the width, length, and height of the room are all equal to <code>n</code> units. You are asked to place <code>n</code> boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:</p>

<ul>
	<li>You can place the boxes anywhere on the floor.</li>
	<li>If box <code>x</code> is placed on top of the box <code>y</code>, then each side of the four vertical sides of the box <code>y</code> <strong>must</strong> either be adjacent to another box or to a wall.</li>
</ul>

<p>Given an integer <code>n</code>, return<em> the <strong>minimum</strong> possible number of boxes touching the floor.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/3-boxes.png" style="width: 135px; height: 143px;" /></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/4-boxes.png" style="width: 135px; height: 179px;" /></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/10-boxes.png" style="width: 271px; height: 257px;" /></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
    long helper(long x) {
        if (x<3) return x;
        long k=(sqrt(1+8.0*x)-1)/2;
        long y=k*(k-1)/2+max(0L, x-k*(k+1)/2-1);
        return x+helper(y);
    }
public:
    int minimumBoxes(int n) {
        int l=1, r=n;
        while (l<r) {
            int m=l+(r-l)/2;
            long count=helper(m);
            if (count<n) l=m+1;
            else r=m;
        }
        return l;    
        
        /*
         * memory limit exceeded
         *
        vector<int> table {0, 0};        
        for (int i=2; i<=n; i++) {
            int b=table.back();
            table.push_back(b);
            for (int j=1; j<i; j++) {
                table.push_back(++b);
            }
        }
        int l=1, r=n;
        while (l<r) {
            int m=l+(r-l)/2;
            int k=m, count=0;
            while (k>0) {
                count+=k;
                k=table[k];
            }
            if (count<n) l=m+1;
            else r=m;
        }
        return l;
        */
    }
};
8500