Maximum Sized Array

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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:

1
2
3
4
5
6


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 n in the range [1, upper_bound] (where upper_bound can be a large enough value, e.g., 10^6).
For each candidate n, compute the sum of all A[i][j][k]:
- For each i from 0 to n-1, sum over all j, k of i * (j | k).
- Use bitwise analysis to count how many times each bit is set in (j | k) and multiply accordingly.
If the sum is within s, try a larger n; otherwise, try smaller.
Return the largest valid n found.

Code

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

 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


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

 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


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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 in O(n log n) using bitwise analysis.
🧺 Space complexity: O(1), only a few variables are used for computation.

Problem#

Examples#

Solution#

Method 1 – Binary Search with Bit Manipulation#

Intuition#

Approach#

Code#

Complexity#