Maximum Sized Array
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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), where0 <= 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.
Examples
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
Solution
Method 1 – Binary Search with Bit Manipulation
Intuition
We need to maximize n such that the sum of all A[i][j][k] = i * (j | k) for 0 <= i, j, k < n does not exceed s. The sum can be computed efficiently using bitwise properties, and we can use binary search to find the largest valid n.
Approach
- Use binary search for
nin the range[1, upper_bound](whereupper_boundcan be a large enough value, e.g.,10^6). - For each candidate
n, compute the sum of allA[i][j][k]:- For each
ifrom0ton-1, sum over allj, kofi * (j | k). - Use bitwise analysis to count how many times each bit is set in
(j | k)and multiply accordingly.
- For each
- If the sum is within
s, try a largern; otherwise, try smaller. - Return the largest valid
nfound.
Code
C++
class Solution {
public:
long long calc(int n) {
long long res = 0;
for (int i = 0; i < n; ++i) {
long long sum = 0;
for (int b = 0; b < 32; ++b) {
long long cnt = 2LL * n * ((n >> b) << b) - ((n >> b) << (b + 1)) + ((n & ((1 << b) - 1)) + 1) * ((n & ((1 << b) - 1)) + 1);
sum += (1LL << b) * cnt;
}
res += i * sum;
}
return res;
}
int maximumSizedArray(long long s) {
int l = 1, r = 1000000, ans = 1;
while (l <= r) {
int m = (l + r) / 2;
if (calc(m) <= s) ans = m, l = m + 1;
else r = m - 1;
}
return ans;
}
};
Go
func calc(n int) int64 {
var res int64
for i := 0; i < n; i++ {
var sum int64
for b := 0; b < 32; b++ {
cnt := int64(2*n*((n>>b)<<b) - ((n>>b)<<(b+1)) + ((n&((1<<b)-1))+1)*((n&((1<<b)-1))+1))
sum += int64(1<<b) * cnt
}
res += int64(i) * sum
}
return res
}
func maximumSizedArray(s int64) int {
l, r, ans := 1, 1000000, 1
for l <= r {
m := (l + r) / 2
if calc(m) <= s {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
Java
class Solution {
private long calc(int n) {
long res = 0;
for (int i = 0; i < n; ++i) {
long sum = 0;
for (int b = 0; b < 32; ++b) {
long cnt = 2L * n * ((n >> b) << b) - ((n >> b) << (b + 1)) + ((n & ((1 << b) - 1)) + 1) * ((n & ((1 << b) - 1)) + 1);
sum += (1L << b) * cnt;
}
res += i * sum;
}
return res;
}
public int maximumSizedArray(long s) {
int l = 1, r = 1000000, ans = 1;
while (l <= r) {
int m = (l + r) / 2;
if (calc(m) <= s) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
}
Kotlin
class Solution {
private fun calc(n: Int): Long {
var res = 0L
for (i in 0 until n) {
var sum = 0L
for (b in 0 until 32) {
val cnt = 2L * n * ((n shr b) shl b) - ((n shr b) shl (b + 1)) + ((n and ((1 shl b) - 1)) + 1).toLong() * ((n and ((1 shl b) - 1)) + 1)
sum += (1L shl b) * cnt
}
res += i * sum
}
return res
}
fun maximumSizedArray(s: Long): Int {
var l = 1; var r = 1000000; var ans = 1
while (l <= r) {
val m = (l + r) / 2
if (calc(m) <= s) { ans = m; l = m + 1 }
else r = m - 1
}
return ans
}
}
Python
class Solution:
def maximumSizedArray(self, s: int) -> int:
def calc(n: int) -> int:
res = 0
for i in range(n):
sum_ = 0
for b in range(32):
cnt = 2 * n * ((n >> b) << b) - ((n >> b) << (b + 1)) + ((n & ((1 << b) - 1)) + 1) ** 2
sum_ += (1 << b) * cnt
res += i * sum_
return res
l, r, ans = 1, 10**6, 1
while l <= r:
m = (l + r) // 2
if calc(m) <= s:
ans = m
l = m + 1
else:
r = m - 1
return ans
Rust
impl Solution {
pub fn maximum_sized_array(s: i64) -> i32 {
fn calc(n: i32) -> i64 {
let mut res = 0i64;
for i in 0..n {
let mut sum = 0i64;
for b in 0..32 {
let cnt = 2 * n as i64 * (((n >> b) << b) as i64) - (((n >> b) << (b + 1)) as i64) + (((n & ((1 << b) - 1)) + 1) as i64).pow(2);
sum += (1i64 << b) * cnt;
}
res += i as i64 * sum;
}
res
}
let (mut l, mut r, mut ans) = (1, 1_000_000, 1);
while l <= r {
let m = (l + r) / 2;
if calc(m) <= s {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
ans
}
}
TypeScript
class Solution {
maximumSizedArray(s: number): number {
function calc(n: number): number {
let res = 0;
for (let i = 0; i < n; ++i) {
let sum = 0;
for (let b = 0; b < 32; ++b) {
let cnt = 2 * n * ((n >> b) << b) - ((n >> b) << (b + 1)) + ((n & ((1 << b) - 1)) + 1) ** 2;
sum += (1 << b) * cnt;
}
res += i * sum;
}
return res;
}
let l = 1, r = 1_000_000, ans = 1;
while (l <= r) {
let m = (l + r) >> 1;
if (calc(m) <= s) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log n log n), where each binary search step computes the sum inO(n log n)using bitwise analysis. - 🧺 Space complexity:
O(1), only a few variables are used for computation.