Skip to content

3806. Maximum Bitwise AND After Increment Operations

Description

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

Solutions

Solution 1: Greedy Bit Construction + Bit Manipulation

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 \(\textit{target}\), we calculate the minimum number of operations required to increase each element in the array to at least \(\textit{target}\).

Specifically, we find the position \(j - 1\) where \(\textit{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 \(\textit{target}\) in the lower \(j\) bits. The required number of operations is \((\textit{target} \& 2^{j} - 1) - (\textit{nums}[i] \& 2^{j} - 1)\). We store the required number of operations for all elements in the array \(\textit{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 \(\textit{nums}\) and \(M\) is the maximum value in the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        mx = (max(nums) + k).bit_length()
        ans = 0
        cost = [0] * len(nums)
        for bit in range(mx - 1, -1, -1):
            target = ans | (1 << bit)
            for i, x in enumerate(nums):
                j = (target & ~x).bit_length()
                mask = (1 << j) - 1
                cost[i] = (target & mask) - (x & mask)
            cost.sort()
            if sum(cost[:m]) <= k:
                ans = target
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int maximumAND(int[] nums, int k, int m) {
        int max = 0;
        for (int x : nums) {
            max = Math.max(max, x);
        }
        max += k;

        int mx = 32 - Integer.numberOfLeadingZeros(max);
        int n = nums.length;

        int ans = 0;
        int[] cost = new int[n];

        for (int bit = mx - 1; bit >= 0; bit--) {
            int target = ans | (1 << bit);
            for (int i = 0; i < n; i++) {
                int x = nums[i];
                int diff = target & ~x;
                int j = diff == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(diff);
                int mask = (1 << j) - 1;
                cost[i] = (target & mask) - (x & mask);
            }
            Arrays.sort(cost);
            long sum = 0;
            for (int i = 0; i < m; i++) {
                sum += cost[i];
            }
            if (sum <= k) {
                ans = target;
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maximumAND(const vector<int>& nums, int k, int m) {
        int max_val = ranges::max(nums) + k;
        int mx = max_val > 0 ? 32 - __builtin_clz(max_val) : 0;

        int ans = 0;
        vector<int> cost(nums.size());

        for (int bit = mx - 1; bit >= 0; bit--) {
            int target = ans | (1 << bit);
            for (size_t i = 0; i < nums.size(); i++) {
                int x = nums[i];
                int diff = target & ~x;
                int j = diff == 0 ? 0 : 32 - __builtin_clz(diff);
                long long mask = (1L << j) - 1;
                cost[i] = (target & mask) - (x & mask);
            }

            ranges::sort(cost);
            long long sum = accumulate(cost.begin(), cost.begin() + m, 0LL);
            if (sum <= k) {
                ans = target;
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func maximumAND(nums []int, k int, m int) int {
    mx := bits.Len(uint(slices.Max(nums) + k))

    ans := 0
    cost := make([]int, len(nums))

    for bit := mx - 1; bit >= 0; bit-- {
        target := ans | (1 << bit)
        for i, x := range nums {
            j := bits.Len(uint(target & ^x))
            mask := (1 << j) - 1
            cost[i] = (target & mask) - (x & mask)
        }
        sort.Ints(cost)
        sum := 0
        for i := 0; i < m; i++ {
            sum += cost[i]
        }
        if sum <= k {
            ans = target
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function maximumAND(nums: number[], k: number, m: number): number {
    const mx = 32 - Math.clz32(Math.max(...nums) + k);

    let ans = 0;
    const n = nums.length;
    const cost = new Array(n);

    for (let bit = mx - 1; bit >= 0; bit--) {
        let target = ans | (1 << bit);
        for (let i = 0; i < n; i++) {
            const x = nums[i];
            const diff = target & ~x;
            const j = diff === 0 ? 0 : 32 - Math.clz32(diff);
            const mask = (1 << j) - 1;
            cost[i] = (target & mask) - (x & mask);
        }
        cost.sort((a, b) => a - b);
        let sum = 0;
        for (let i = 0; i < m; i++) {
            sum += cost[i];
        }
        if (sum <= k) {
            ans = target;
        }
    }

    return ans;
}

Comments