Skip to content

3344. Maximum Sized Array πŸ”’

Description

Given a positive integer s, let A be a 3D array of dimensions n × n × n, where each element A[i][j][k] is defined as:

  • A[i][j][k] = i * (j OR k), where 0 <= i, j, k < n.

Return the maximum possible value of n such that the sum of all elements in array A does not exceed s.

 

Example 1:

Input: s = 10

Output: 2

Explanation:

  • Elements of the array A for n = 2:
    • A[0][0][0] = 0 * (0 OR 0) = 0
    • A[0][0][1] = 0 * (0 OR 1) = 0
    • A[0][1][0] = 0 * (1 OR 0) = 0
    • A[0][1][1] = 0 * (1 OR 1) = 0
    • A[1][0][0] = 1 * (0 OR 0) = 0
    • A[1][0][1] = 1 * (0 OR 1) = 1
    • A[1][1][0] = 1 * (1 OR 0) = 1
    • A[1][1][1] = 1 * (1 OR 1) = 1
  • The total sum of the elements in array A is 3, which does not exceed 10, so the maximum possible value of n is 2.

Example 2:

Input: s = 0

Output: 1

Explanation:

  • Elements of the array A for n = 1:
    • A[0][0][0] = 0 * (0 OR 0) = 0
  • The total sum of the elements in array A is 0, which does not exceed 0, so the maximum possible value of n is 1.

 

Constraints:

  • 0 <= s <= 1015

Solutions

We can roughly estimate the maximum value of $n$. For $j \lor k$, the sum of the results is approximately $n^2 (n - 1) / 2$. Multiplying this by each $i \in [0, n)$, the result is approximately $(n-1)^5 / 4$. To ensure $(n - 1)^5 / 4 \leq s$, we have $n \leq 1320$.

Therefore, we can preprocess $f[n] = \sum_{i=0}^{n-1} \sum_{j=0}^{i} (i \lor j)$, and then use binary search to find the largest $n$ such that $f[n-1] \cdot (n-1) \cdot n / 2 \leq s$.

In terms of time complexity, the preprocessing has a time complexity of $O(n^2)$, and the binary search has a time complexity of $O(\log n)$. Therefore, the total time complexity is $O(n^2 + \log n)$. The space complexity is $O(n)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
mx = 1330
f = [0] * mx
for i in range(1, mx):
    f[i] = f[i - 1] + i
    for j in range(i):
        f[i] += 2 * (i | j)


class Solution:
    def maxSizedArray(self, s: int) -> int:
        l, r = 1, mx
        while l < r:
            m = (l + r + 1) >> 1
            if f[m - 1] * (m - 1) * m // 2 <= s:
                l = m
            else:
                r = m - 1
        return l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private static final int MX = 1330;
    private static final long[] f = new long[MX];
    static {
        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);
            }
        }
    }
    public int maxSizedArray(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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const MX = 1330

var f [MX]int64

func init() {
    f[0] = 0
    for i := 1; i < MX; i++ {
        f[i] =