LeetCode 3806 - Maximum Bitwise AND After Increment Operations

The problem asks us to find the maximum possible bitwise AND of any subset of size m from an array nums after performing up to k increment operations. Each operation allows us to increase any element in the array by 1.

leetcodehardarraygreedybit-manipulationsorting

LeetCode Problem 3806

Difficulty: 🔴 Hard
Topics: Array, Greedy, Bit Manipulation, Sorting

Solution

Problem Understanding

The problem asks us to find the maximum possible bitwise AND of any subset of size m from an array nums after performing up to k increment operations. Each operation allows us to increase any element in the array by 1. The output is the largest integer that can be obtained as the bitwise AND of some subset of exactly m numbers after using the operations optimally.

Restated, we are allowed to carefully distribute at most k increments across the array so that when we choose a subset of size m, the bitwise AND of that subset is maximized. The bitwise AND operation only retains bits that are 1 in all numbers, so the key challenge is identifying which bits can be set to 1 across at least m elements using at most k operations.

Constraints tell us that nums can be up to 50,000 elements, each up to 1e9, and k can be up to 1e9. This rules out brute-force solutions that try all subsets or attempt to enumerate all possibilities of increasing elements individually. Edge cases include very small arrays, k being very large relative to nums, and cases where m equals the array length.

Approaches

The brute-force approach would involve trying all subsets of size m and simulating all ways to distribute the k increment operations to maximize the bitwise AND. This is infeasible because there are combinatorially many subsets and increment distributions, leading to exponential complexity.

The key insight for an optimal solution comes from bit manipulation and greedy selection. Since bitwise AND requires all chosen numbers to have a 1 in a specific position, we can consider the solution bit by bit from the highest bit to the lowest. For each bit, we check whether it is possible to set that bit in at least m numbers using at most k operations. We do this by calculating the number of operations required to set this bit in each number and choosing the m numbers that need the fewest increments. If we can afford it, we include that bit in the final AND and reduce k accordingly. This approach efficiently narrows down the candidate AND value using a greedy strategy guided by the bit representation.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, m) * ?) O(?) Enumerates all subsets of size m and possible increments, infeasible for n ~ 5e4
Optimal O(n * log(max_num)) O(n) Greedy + bit manipulation, checks each bit from high to low and selects m numbers needing minimal increments

Algorithm Walkthrough

  1. Initialize a variable result to 0. This will store the maximum AND we can achieve.
  2. Iterate through each bit from the 30th (since nums[i] <= 1e9 < 2^30) down to the 0th bit.
  3. For the current bit, calculate the number of increment operations needed to ensure that this bit is set in each number. If a number already has this bit set, it requires 0 operations. Otherwise, compute the minimum increment to set this bit.
  4. Sort the required operations and sum the smallest m of them.
  5. If the sum of operations for the m numbers is less than or equal to k, it is possible to set this bit for a subset of size m. Add this bit to result and reduce k accordingly.
  6. Continue to the next lower bit and repeat the process.
  7. After all bits are processed, result contains the maximum achievable bitwise AND.

Why it works: At each bit, we greedily ensure that it can be included in the AND of m numbers if possible. Since higher bits contribute more to the AND value, processing from highest to lowest ensures that we maximize the AND. The greedy check guarantees that no bit is included unless feasible with the remaining operations.

Python Solution

from typing import List

class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        result = 0
        n = len(nums)
        for bit in reversed(range(31)):  # From 30 down to 0
            needed_ops = []
            for num in nums:
                if num & (1 << bit):
                    needed_ops.append(0)
                else:
                    increment = ((num | (1 << bit)) - num)
                    needed_ops.append(increment)
            needed_ops.sort()
            if sum(needed_ops[:m]) <= k:
                result |= (1 << bit)
        return result

In this Python solution, we iterate from the highest to the lowest bit and determine the cost to set each bit. Sorting ensures that we can choose the m numbers requiring minimal increments. By checking the sum against k, we only include feasible bits, building the result greedily.

Go Solution

import "sort"

func maximumAND(nums []int, k int, m int) int {
    result := 0
    n := len(nums)
    for bit := 30; bit >= 0; bit-- {
        neededOps := make([]int, n)
        for i, num := range nums {
            if num&(1<<bit) != 0 {
                neededOps[i] = 0
            } else {
                neededOps[i] = (num | (1 << bit)) - num
            }
        }
        sort.Ints(neededOps)
        sum := 0
        for i := 0; i < m; i++ {
            sum += neededOps[i]
        }
        if sum <= k {
            result |= (1 << bit)
        }
    }
    return result
}

The Go implementation mirrors the Python logic. We initialize a slice to store the needed operations, sort it, and check whether we can afford to set the bit in the top m numbers. Go requires explicit slice allocation, and integer arithmetic is safe since constraints are within int limits.

Worked Examples

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

Bit Needed Operations Top 2 sum <= k? Result
2 (4) [1,3,2] 1+2=3 <= 8 result
1 (2) [2,1,0] 0+1=1 <= 8 result
0 (1) [1,0,0] 0+0=0 <= 8 result

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

Processing top bits ensures we include only feasible bits, yielding result = 4 after the algorithm.

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(max_num) + n log n * log(max_num)) ≈ O(n log max_num) For each of 31 bits, we calculate increments for n numbers and sort them to choose top m
Space O(n) Store required operations for n numbers

The algorithm is efficient enough given n ≤ 5e4 and 31 bits.

Test Cases

# Provided examples
assert Solution().maximumAND([3,1,2], 8, 2) == 6  # Example 1
assert Solution().maximumAND([1,2,8,4], 7, 3) == 4  # Example 2
assert Solution().maximumAND([1,1], 3, 2) == 2  # Example 3

# Edge / additional cases
assert Solution().maximumAND([1,2,3], 0, 2) == 2  # No operations allowed
assert Solution().maximumAND([1,1,1,1], 10, 4) == 1  # Can increase all but only result is 1 (all bits same)
assert Solution().maximumAND([5,5,5], 3, 2) == 5  # Already maximal AND
assert Solution().maximumAND([0,0,0], 6, 2) == 3  # Use operations to set top 2 bits
Test Why
Example 1 Verifies basic operation distribution and maximal AND
Example 2 Tests larger k relative to numbers and subset selection
Example 3 Minimal array, simple increments
No operations Tests handling k=0
All ones Tests scenario where incrementing not needed for AND
Already maximal Tests early termination when nums already allow maximal AND
Zeroes Tests incrementing multiple elements to achieve high AND

Edge Cases

1. k = 0: When no operations are allowed, the algorithm should only consider the original numbers. Our approach correctly calculates needed operations as 0 for bits already set and ignores bits that cannot be achieved without increments.

2. Subset size m = n: When the subset must include all numbers, we must ensure bits are set across the entire array. The algorithm sums operations for all n elements and includes a bit only if total operations ≤ k, correctly handling this edge case.

3. Large k relative to nums: When `