Skip to content

Latest commit

 

History

History
253 lines (200 loc) · 6.04 KB

README_EN.md

File metadata and controls

253 lines (200 loc) · 6.04 KB
Raw
comments difficulty edit_url tags
true
Medium
Bit Manipulation
Binary Search

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: 
    <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>

Example 2:

Input: s = 0

Output: 1

Explanation:

  • Elements of the array A for n = 1: 
    <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>

 

Constraints:

  • 0 <= s <= 1015

Solutions

Solution 1: Preprocessing + Binary Search

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)$.

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

const MX = 1330

var f [MX]int64

func init() {
	f[0] = 0
	for i := 1; i < MX; i++ {
		f[i] = f[i-1] + int64(i)
		for j := 0; j < i; j++ {
			f[i] += 2 * int64(i|j)
		}
	}
}

func maxSizedArray(s int64) int {
	l, r := 1, MX
	for l < r {
		m := (l + r + 1) >> 1
		if f[m-1]*int64(m-1)*int64(m)/2 <= s {
			l = m
		} else {
			r = m - 1
		}
	}
	return l
}

TypeScript

const MX = 1330;
const f: bigint[] = Array(MX).fill(0n);
(() => {
    f[0] = 0n;
    for (let i = 1; i < MX; i++) {
        f[i] = f[i - 1] + BigInt(i);
        for (let j = 0; j < i; j++) {
            f[i] += BigInt(2) * BigInt(i | j);
        }
    }
})();

function maxSizedArray(s: number): number {
    let l = 1,
        r = MX;
    const target = BigInt(s);

    while (l < r) {
        const m = (l + r + 1) >> 1;
        if ((f[m - 1] * BigInt(m - 1) * BigInt(m)) / BigInt(2) <= target) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    return l;
}