Maximum Sized Array - Solution & Explanation

Problem Overview: You need to determine the maximum possible array size n such that the total cost defined by specific bit positions across numbers 1..n does not exceed a given limit. The challenge is computing this cost efficiently without iterating through every number.

Approach 1: Direct Simulation (Brute Force) (Time: O(n log n), Space: O(1))

The most straightforward idea is to iterate through every number from 1 to n, examine its binary representation, and count the bits that contribute to the cost based on the rule (for example, specific bit positions). Accumulate this cost until the limit is exceeded. While this approach is simple to reason about, it becomes infeasible for large n because each number requires inspecting its bits. Even with efficient bit operations, the total work grows linearly with n.

Approach 2: Preprocessing + Binary Search (Time: O(log n * log n), Space: O(1))

The key observation is that the cost function is monotonic: as n increases, the total cost for the range 1..n never decreases. This property allows you to apply binary search on the answer. Instead of constructing the array, you guess a candidate size mid and compute the total cost contributed by all numbers from 1 to mid. If the cost stays within the allowed limit, the size is feasible and you search to the right; otherwise you search to the left.

The remaining problem is computing the contribution of each bit position efficiently. Using patterns in binary representations, you can count how many numbers in 1..mid have a specific bit set. For a bit position b, the pattern repeats every 2^(b+1) numbers. Half of each cycle contributes a set bit. This lets you compute counts in O(1) per bit instead of scanning every number. Only the relevant positions (for example those divisible by a given constraint) need to be considered. This technique relies heavily on bit manipulation and simple arithmetic patterns.

Combining these ideas gives a fast feasibility check inside binary search. Each check iterates through possible bit positions (roughly log n of them) and accumulates their contributions. The binary search itself also runs for log n steps, making the overall complexity O(log n * log n), which easily handles very large ranges.

Recommended for interviews: The preprocessing + binary search approach is the expected solution. Brute force demonstrates understanding of the cost definition, but recognizing the monotonic property and applying binary search with bit-counting formulas shows strong algorithmic thinking and familiarity with bit manipulation patterns.