LeetCode Problem 3344

Difficulty: 🟡 Medium
Topics: Binary Search, Bit Manipulation

Solution

LeetCode 3344 - Maximum Sized Array

Problem Understanding

We are given a non-negative integer s and need to determine the largest possible dimension n of a three-dimensional array A.

The array has dimensions n × n × n, and every element is defined as:

$$A[i][j][k] = i \times (j ;|; k)$$

where | denotes the bitwise OR operation.

The goal is to find the maximum value of n such that the sum of all array elements does not exceed s.

Formally, we need the largest n satisfying:

$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{k=0}^{n-1} i \cdot (j|k) \le s$$

The constraint s ≤ 10^15 is the key observation. A direct simulation of even moderately large arrays is impossible. The total number of elements is n³, and the answer can be around one thousand, so iterating over all triples would require billions of operations.

The problem guarantees that s is non-negative. An important edge case is s = 0. Since the array of size 1 × 1 × 1 contains only a single zero, the answer is at least 1.

Another important observation is that the total sum grows monotonically as n increases. If a certain value of n is valid, then every smaller value is also valid. This monotonicity strongly suggests binary search.

Approaches

Brute Force

The most straightforward approach is to try increasing values of n, explicitly compute:

$$\sum i \cdot (j|k)$$

for all triples (i,j,k), and stop once the sum exceeds s.

This approach is obviously correct because it directly follows the definition of the array.

However, its complexity is terrible. Computing the sum for one value of n requires O(n³) operations. Since the answer can be around 1200, this is completely infeasible.

Key Insight

The formula separates naturally:

$$\sum_{i,j,k} i\cdot(j|k) = \left(\sum_{i=0}^{n-1} i\right) \left(\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}(j|k)\right)$$

The first factor is simply:

$$\frac{n(n-1)}{2}$$

Therefore, the entire problem reduces to efficiently computing:

$$F(n)=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}(j|k)$$

Instead of evaluating every pair (j,k), we examine each bit independently.

For a bit position b, let:

• ones = numbers in [0,n-1] whose b-th bit is set
• zeros = n - ones

The OR result has bit b equal to 0 only when both numbers have that bit equal to 0.

Thus:

$$\text{pairs with bit } b \text{ set} = n^2 - zeros^2$$

Each such pair contributes 2^b.

Hence:

$$F(n) = \sum_b (n^2-zeros_b^2)\cdot 2^b$$

We can compute the number of set bits in [0,n-1] for every bit position in O(log n) time.

After obtaining F(n), the total array sum becomes:

$$\frac{n(n-1)}{2}\cdot F(n)$$

Since this value grows monotonically with n, we can binary search for the largest valid dimension. This bit-counting approach is a standard decomposition of OR sums.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³) per check	O(1)	Directly evaluates every array element
Optimal	O(log² n)	O(1)	Binary search plus bitwise counting

Algorithm Walkthrough

1. Define a helper function that counts how many numbers in [0, n-1] have a particular bit position set.
2. For a given bit b, numbers repeat in blocks of length 2^(b+1). In each complete block, exactly 2^b numbers have that bit set.
3. Use the block pattern to compute the number of set bits in O(1) time for that bit.
4. For every bit position that may appear in numbers below n, compute:

$$ones_b$$

and

$$zeros_b=n-ones_b$$ 5. Count how many ordered pairs (j,k) produce a set bit in their OR:

$$n^2-zeros_b^2$$ 6. Multiply by the bit value 2^b and add it to the OR-sum:

$$F(n)$$ 7. Compute:

$$\text{total}(n) = \frac{n(n-1)}{2} \cdot F(n)$$ 8. Binary search on n. If total(n) ≤ s, the dimension is feasible and we try larger values. Otherwise we move left. 9. Return the largest feasible value.

Why it works

The crucial invariant is that each bit contributes independently to the OR operation. For every bit position, we count exactly how many (j,k) pairs produce that bit in (j|k). Summing those independent contributions reconstructs the exact OR-sum.

The total array sum factors into the product of the OR-sum and the arithmetic sum of all i values. Therefore total(n) is computed exactly. Since total(n) increases as n increases, binary search correctly finds the largest feasible dimension.

Python Solution

class Solution:
    def maxSizedArray(self, s: int) -> int:
        def count_ones(n: int, bit: int) -> int:
            block = 1 << bit
            cycle = block << 1

            full_cycles = n // cycle
            remainder = n % cycle

            return full_cycles * block + max(0, remainder - block)

        def total_sum(n: int) -> int:
            or_sum = 0

            bit = 0
            while (1 << bit) < n:
                ones = count_ones(n, bit)
                zeros = n - ones

                pairs_with_bit = n * n - zeros * zeros
                or_sum += pairs_with_bit * (1 << bit)

                bit += 1

            return or_sum * n * (n - 1) // 2

        if s == 0:
            return 1

        left = 1
        right = 2000

        while left < right:
            mid = (left + right + 1) // 2

            if total_sum(mid) <= s:
                left = mid
            else:
                right = mid - 1

        return left

Implementation Explanation

The count_ones helper computes how many integers in [0,n-1] contain a particular bit. This uses the standard repeating pattern of binary digits.

The total_sum helper evaluates the complete array sum for a candidate dimension n. Instead of enumerating all pairs (j,k), it processes each bit independently. For every bit, it computes how many ordered pairs have that bit present in their OR result.

Once the OR-sum is known, multiplying by:

$$\frac{n(n-1)}{2}$$

accounts for the contribution of the i dimension.

The main routine performs binary search over possible dimensions. The upper bound 2000 is safely above the maximum answer for s ≤ 10^{15}. The search keeps the largest feasible value.

Go Solution

func maxSizedArray(s int64) int {
	countOnes := func(n int64, bit int) int64 {
		block := int64(1 << bit)
		cycle := block << 1

		fullCycles := n / cycle
		remainder := n % cycle

		extra := int64(0)
		if remainder > block {
			extra = remainder - block
		}

		return fullCycles*block + extra
	}

	totalSum := func(n int64) int64 {
		var orSum int64 = 0

		for bit := 0; (int64(1) << bit) < n; bit++ {
			ones := countOnes(n, bit)
			zeros := n - ones

			pairsWithBit := n*n - zeros*zeros
			orSum += pairsWithBit * (int64(1) << bit)
		}

		return orSum * n * (n - 1) / 2
	}

	if s == 0 {
		return 1
	}

	left, right := int64(1), int64(2000)

	for left < right {
		mid := (left + right + 1) / 2

		if totalSum(mid) <= s {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return int(left)
}

Go Specific Notes

The logic is identical to the Python version. The main difference is the use of int64 throughout the computation because intermediate values can reach approximately 10^15.

All arithmetic is performed using integer operations, so there are no floating point precision concerns.

Worked Examples

Example 1

Input:

s = 10

Binary search checks n = 2.

For bit 0:

Value	Count
ones	1
zeros	1

Number of pairs with bit set:

$$2^2-1^2=3$$

Contribution:

$$3\times1=3$$

So:

$$F(2)=3$$

Arithmetic sum of i values:

$$0+1=1$$

Total:

$$1\times3=3$$

Since:

$$3 \le 10$$

n = 2 is valid.

For n = 3:

$$F(3)=15$$

Arithmetic sum:

$$0+1+2=3$$

Total:

$$45$$

Since:

$$45>10$$

n = 3 is invalid.

Answer:

2

Example 2

Input:

s = 0

For n = 1:

$$A[0][0][0]=0$$

Total sum:

$$0$$

which satisfies the constraint.

Any larger dimension produces a positive sum.

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log² n)	Binary search performs O(log n) checks, each check processes O(log n) bits
Space	O(1)	Only a few variables are stored

The bit-counting routine iterates over at most about 11 to 12 bits because the answer is around 1200. Binary search also requires about 11 iterations. Therefore the actual running time is extremely small.

Test Cases

sol = Solution()

assert sol.maxSizedArray(0) == 1      # minimum input
assert sol.maxSizedArray(10) == 2     # example 1

assert sol.maxSizedArray(3) == 2      # exactly fits n=2
assert sol.maxSizedArray(2) == 1      # just below threshold for n=2

assert sol.maxSizedArray(44) == 2     # one below n=3 requirement
assert sol.maxSizedArray(45) == 3     # exactly fits n=3

assert sol.maxSizedArray(46) == 3     # slightly above n=3 threshold

assert sol.maxSizedArray(10**15) >= 1 # maximum constraint

Test Summary

Test	Why
s = 0	Smallest possible input
s = 10	Official example
s = 3	Exact boundary for n = 2
s = 2	Just below a valid threshold
s = 44	One less than n = 3 requirement
s = 45	Exact threshold for n = 3
s = 46	Just above threshold
s = 10^15	Maximum constraint

Edge Cases

Edge Case 1, s = 0

This is the smallest allowed input. A common bug is returning 0, but the problem asks for the maximum valid dimension, and n = 1 already produces a total sum of zero. The implementation explicitly handles this case and returns 1.

Edge Case 2, Exact Threshold Values

When s equals the exact sum produced by some dimension n, the answer must still be n. Binary search uses the condition <= s to treat equality as feasible, ensuring these boundary cases are handled correctly.

Edge Case 3, Large Inputs Near 10^15

Intermediate values become very large. Using floating point arithmetic could introduce precision errors and cause incorrect binary search decisions. The implementation uses only integer arithmetic, ensuring exact results even near the maximum constraint.

Edge Case 4, Bit Positions Beyond the Highest Set Bit

For small values of n, many bit positions contribute nothing. The implementation stops once 2^bit >= n, preventing unnecessary work and avoiding accidental overcounting of nonexistent bits.