Maximum Sized Array
<p>Given a positive integer <code>s</code>, let <code>A</code> be a 3D array of dimensions<!-- notionvc: f8069282-c5f5-4da1-91b8-fa0c1c168ea1 --> <code>n &times; n &times; n</code>, where each element <code>A[i][j][k]</code> is defined as:</p>

<ul>
	<li><code>A[i][j][k] = i * (j OR k)</code>, where <code>0 &lt;= i, j, k &lt; n</code>.</li>
</ul>

<p>Return the <strong>maximum</strong> possible value of <code>n</code> such that the <strong>sum</strong> of all elements in array <code>A</code> does not exceed <code>s</code>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = 10</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Elements of the array <code>A</code> for <code>n = 2</code><strong>:</strong>

    <ul>
    	<li><code>A[0][0][0] = 0 * (0 OR 0) = 0</code></li>
    	<li><code>A[0][0][1] = 0 * (0 OR 1) = 0</code></li>
    	<li><code>A[0][1][0] = 0 * (1 OR 0) = 0</code></li>
    	<li><code>A[0][1][1] = 0 * (1 OR 1) = 0</code></li>
    	<li><code>A[1][0][0] = 1 * (0 OR 0) = 0</code></li>
    	<li><code>A[1][0][1] = 1 * (0 OR 1) = 1</code></li>
    	<li><code>A[1][1][0] = 1 * (1 OR 0) = 1</code></li>
    	<li><code>A[1][1][1] = 1 * (1 OR 1) = 1</code></li>
    </ul>
    </li>
    <li>The total sum of the elements in array <code>A</code> is 3, which does not exceed 10, so the maximum possible value of <code>n</code> is 2.</li>

</ul>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = 0</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Elements of the array <code>A</code> for <code>n = 1</code>:

    <ul>
    	<li><code>A[0][0][0] = 0 * (0 OR 0) = 0</code></li>
    </ul>
    </li>
    <li>The total sum of the elements in array <code>A</code> is 0, which does not exceed 0, so the maximum possible value of <code>n</code> is 1.</li>

</ul>
</div>

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

<ul>
	<li><code>0 &lt;= s &lt;= 10<sup>15</sup></code></li>
</ul>
Bit Manipulation; Binary Search
const int MX = 1330;
long long f[MX];
auto init = [] {
    f[0] = 0;
    for (int i = 1; i < MX; ++i) {
        f[i] = f[i - 1] + i;
        for (int j = 0; j < i; ++j) {
            f[i] += 2 * (i | j);
        }
    }
    return 0;
}();

class Solution {
public:
    int maxSizedArray(long long s) {
        int l = 1, r = MX;
        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (f[m - 1] * (m - 1) * m / 2 <= s) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
};
