You are given a 0-indexed integer array nums and an integer k.
In one operation, you can pick any index i of nums such that 0 <= i < nums.length - 1 and replace nums[i] and nums[i + 1] with a single occurrence of nums[i] & nums[i + 1], where & represents the bitwise AND operator.
Return the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Example 1:
Input: nums = [3,5,3,2,7], k = 2 Output: 3 Explanation: Let's do the following operations: 1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [1,3,2,7]. 2. Replace nums[2] and nums[3] with (nums[2] & nums[3]) so that nums becomes equal to [1,3,2]. The bitwise-or of the final array is 3. It can be shown that 3 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Example 2:
Input: nums = [7,3,15,14,2,8], k = 4 Output: 2 Explanation: Let's do the following operations: 1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,15,14,2,8]. 2. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,14,2,8]. 3. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [2,2,8]. 4. Replace nums[1] and nums[2] with (nums[1] & nums[2]) so that nums becomes equal to [2,0]. The bitwise-or of the final array is 2. It can be shown that 2 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Example 3:
Input: nums = [10,7,10,3,9,14,9,4], k = 1 Output: 15 Explanation: Without applying any operations, the bitwise-or of nums is 15. It can be shown that 15 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Constraints:
1 <= nums.length <= 1050 <= nums[i] < 2300 <= k < nums.lengthProblem Overview: You are given an array and allowed to perform up to k operations where two adjacent elements can be replaced with their bitwise AND. After all operations, compute the bitwise OR of the remaining elements. The goal is to minimize this final OR value.
Approach 1: Greedy Bit Elimination Using AND Segments (O(n log M) time, O(1) space)
The key observation: if a bit appears in the final OR, at least one remaining element must contain that bit. To minimize the OR, you try to eliminate higher bits first. Iterate bits from most significant to least significant and check whether it's possible to keep that bit 0 in the result. During the check, scan the array and greedily combine adjacent numbers using AND. Once the running AND removes the target bit, you form a segment. If the number of required merges stays within k, that bit can remain 0. Otherwise the bit must be set in the answer. This works because AND operations only remove bits, never introduce them. The technique relies heavily on properties of bit manipulation and a greedy feasibility check.
Approach 2: Optimize by Pairing Strategically (O(n log M) time, O(1) space)
Another way to think about the problem is grouping numbers into segments whose cumulative AND eliminates unwanted bits. While scanning the array, maintain a running AND value. If the current segment still contains a forbidden bit, extend the segment and keep applying AND with the next element. When the bit disappears, finalize the segment and start a new one. Each finalized segment corresponds to merges performed inside it. The greedy decision is to close a segment as soon as it becomes valid so you minimize the number of operations used. This approach effectively simulates optimal pairings and avoids exploring exponential combinations. The logic aligns with techniques commonly used in greedy algorithms and bitwise aggregation in array problems.
Recommended for interviews: The greedy bit elimination approach. Interviewers expect candidates to reason about bitwise behavior: AND only clears bits, OR accumulates bits. Demonstrating the feasibility check for each bit shows strong understanding of greedy strategies combined with bit manipulation. Brute reasoning about pair combinations shows intuition, but the bitwise greedy solution proves algorithmic maturity.
This approach entails making strategic AND operations to gradually minimize the elements in the array. By iterating through the list and focusing on adjacent pairs, we can reduce the number of elements while minimizing alterations to the overall OR value of the list.
The strategy involves iterating through the list nums. If possible, i.e., if k>0, replace each element by the conjunction of itself and the next element. After these operations, compute the bitwise OR of the resulting array.
Time Complexity: O(n), where n is the number of elements in nums, as we iterate through the list once.
Space Complexity: O(1), because operations are performed in-place.
This approach focuses on extensively using AND operations between strategically chosen pairs. The key idea is using operations on elements yielding the largest reduction in OR, thus minimizing the result.
Every possible AND sequence used maximizes bit cancellation over adjacent pairs to lower OR, scanning neighborhood proximity repeatedly for optimal combination.
Time Complexity: O(n * k), nested iteration controlled by k auto-limiting.
Space Complexity: O(1), absence of dynamically allocated accompanying supplemental storage.
| Approach | Complexity |
|---|---|
| Greedy Approach based on AND and OR operations | Time Complexity: O(n), where n is the number of elements in |
| Optimize by Pairing Strategically | Time Complexity: O(n * k), nested iteration controlled by |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Bit Elimination with Feasibility Check | O(n log M) | O(1) | Best general solution. Efficient for large arrays and typical interview constraints. |
| Strategic Pairing with Running AND Segments | O(n log M) | O(1) | Useful for understanding how segment merges simulate optimal pair operations. |
3022. Minimize OR of Remaining Elements Using Operations | Weekly Leetcode 382 • codingMohan • 2,659 views views
Watch 4 more video solutions →Practice Minimize OR of Remaining Elements Using Operations with our built-in code editor and test cases.
Practice on FleetCode