Welcome to Subscribe On Youtube
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] = 3to 6 using 3 operations, and increasenums[2] = 2to 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 is6, 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] = 1to 4 using 3 operations, increasenums[1] = 2to 4 using 2 operations, and keepnums[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 * 1041 <= nums[i] <= 1091 <= k <= 1091 <= 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}$.
-
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; } } -
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; } }; -
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 -
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 } -
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; }