Maximum Bitwise AND After Increment Operations - Solution & Explanation

Problem Overview: You are given an array and a limited number of increment operations. Each operation increases an element by 1. The goal is to perform these increments so the bitwise AND of all array elements becomes as large as possible.

Approach 1: Increment Simulation / Brute Force (Exponential / Impractical)

A naive strategy tries distributing increments across elements in different ways and computes the resulting AND. Because each element can receive multiple increments, the number of possible states grows extremely fast. Even with pruning, exploring all increment distributions quickly becomes infeasible for typical constraints. Time complexity grows exponentially with the number of operations, and space complexity is also exponential due to state tracking. This approach is mainly useful for understanding the search space or validating small test cases.

Approach 2: Greedy Bit Construction + Bit Manipulation (O(n log M))

The optimal strategy builds the final AND value one bit at a time from the most significant bit to the least. If the final AND contains a bit, every number must have that bit set after increments. For a candidate bit, compute how many increments each element needs to reach the smallest number that preserves previously chosen bits and sets the current bit. This uses bit operations and rounding logic to find the next valid value. Sum the required increments across the array and check if the total fits within k. If it does, keep the bit and subtract the cost; otherwise skip it. This greedy construction works because higher bits contribute more to the final value, so locking them first maximizes the result.

The algorithm iterates through ~30–60 bits depending on integer size. For each bit, it scans the array and calculates the minimal increments required to make the bit valid while preserving previously fixed bits. Time complexity is O(n log M) where M is the maximum value range, and space complexity is O(1).

Recommended for interviews: The greedy bit construction approach is what interviewers expect. Brute force demonstrates understanding of the objective but does not scale. Using bit manipulation to construct the answer and applying a greedy decision process over bits shows strong reasoning about binary properties. The array is scanned repeatedly but remains simple, making the solution both efficient and clean. This pattern appears frequently in problems involving maximizing bitwise results over an array using greedy decisions.