Skip to main content
Talentd

Maximum Bitwise AND After Increment Operations - Solution & Explanation

HardArrayGreedyBit ManipulationSorting12 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given an integer array nums and two integers k and m.

You may perform at most k operations. In one operation, you may choose any index i and increase nums[i] by 1.

Return an integer denoting the maximum possible bitwise AND of any subset of size m after performing up to k operations optimally.

 

Example 1:

Input: nums = [3,1,2], k = 8, m = 2

Output: 6

Explanation:

  • We need a subset of size m = 2. Choose indices [0, 2].
  • Increase nums[0] = 3 to 6 using 3 operations, and increase nums[2] = 2 to 6 using 4 operations.
  • The total number of operations used is 7, which is not greater than k = 8.
  • The two chosen values become [6, 6], and their bitwise AND is 6, which is the maximum possible.

Example 2:

Input: nums = [1,2,8,4], k = 7, m = 3

Output: 4

Explanation:

  • We need a subset of size m = 3. Choose indices [0, 1, 3].
  • Increase nums[0] = 1 to 4 using 3 operations, increase nums[1] = 2 to 4 using 2 operations, and keep nums[3] = 4.
  • The total number of operations used is 5, which is not greater than k = 7.
  • The three chosen values become [4, 4, 4], and their bitwise AND is 4, which is the maximum possible.​​​​​​​

Example 3:

Input: nums = [1,1], k = 3, m = 2

Output: 2

Explanation:

  • We need a subset of size m = 2. Choose indices [0, 1].
  • Increase both values from 1 to 2 using 1 operation each.
  • The total number of operations used is 2, which is not greater than k = 3.
  • The two chosen values become [2, 2], and their bitwise AND is 2, which is the maximum possible.

 

Constraints:

  • 1 <= n == nums.length <= 5 * 104
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109
  • 1 <= m <= n

Approach Overview

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.

Solution

We enumerate each bit from the highest bit, attempting to include that bit in the final bitwise AND result. For the currently attempted bitwise AND result target, we calculate the minimum number of operations required to increase each element in the array to at least target.

Specifically, we find the position j - 1 where target has the first bit set to 1 from high to low, while the current element has the corresponding bit set to 0. Then we only need to increase the current element to the value of target in the lower j bits. The required number of operations is (target \& 2^{j} - 1) - (nums[i] \& 2^{j} - 1). We store the required number of operations for all elements in the array cost, sort it, and take the sum of the first m elements. If it does not exceed k, it means we can include this bit in the final bitwise AND result.

The time complexity is O(n times log n times log M) and the space complexity is O(n), where n is the length of the array nums and M is the maximum value in the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Increment Distribution Brute ForceExponentialExponentialOnly for very small inputs or conceptual understanding of the search space
Greedy Bit Construction + Bit ManipulationO(n log M)O(1)General case. Efficient when values fit within typical 32–60 bit integers

Video Solution

Q4. Maximum Bitwise AND After Increment Operations || Very Easy Approach || Leetcode Weekly 484 🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 1,040 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Bitwise AND After Increment Operations easy or hard?
Maximum Bitwise AND After Increment Operations is classified as Hard because it requires combining greedy reasoning with bit manipulation. The main challenge is recognizing that the final AND value can be constructed bit by bit while checking feasibility using increment costs.
Maximum Bitwise AND After Increment Operations Python/Java solution
Most implementations follow the same greedy bit-building logic. Iterate from the highest bit to the lowest, compute required increments for each array element, and track whether the total cost fits within k. This logic translates cleanly into Python, Java, C++, Go, and TypeScript.
How to solve Maximum Bitwise AND After Increment Operations in O(n log M)?
Construct the answer bit by bit from the highest bit downward. For each candidate bit, compute how many increments each element needs to reach the nearest value that preserves previously chosen bits and sets the current bit. If the total increments stay within k, keep the bit and deduct the cost. Otherwise skip the bit and continue.
What is the best approach for Maximum Bitwise AND After Increment Operations?
The most effective solution uses greedy bit construction with bit manipulation. Build the result from the most significant bit to the least and check whether all numbers can be incremented to satisfy that bit within the allowed operations. This works because higher bits contribute more to the final AND value. The overall complexity is O(n log M).
Is Maximum Bitwise AND After Increment Operations asked at Google/Amazon/Meta?
Bit manipulation and greedy optimization problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The exact problem may vary, but the pattern of maximizing a bitwise result under constraints is frequently tested in senior algorithm rounds.
What data structure is used in Maximum Bitwise AND After Increment Operations?
The solution mainly relies on arrays and bit manipulation operations. The algorithm repeatedly scans the array to compute increment costs for candidate bits. No advanced data structures are required, which keeps space usage constant.
What is the time complexity of Maximum Bitwise AND After Increment Operations?
The optimal greedy approach runs in O(n log M), where n is the array size and M is the maximum possible integer value. The algorithm checks each bit position (typically up to 30–60 bits) and scans the array to compute required increments. Space complexity remains O(1) since only a few variables are maintained.

Ready to solve this problem?

Practice Maximum Bitwise AND After Increment Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays