Minimize OR of Remaining Elements Using Operations - Solution & Explanation
Problem Statement
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.length
Approach Overview
Problem 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.
Approach 1: Greedy Approach based on AND and OR operations
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.
Complexity
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.
Approach 2: Optimize by Pairing Strategically
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.
Complexity
Time Complexity: O(n * k), nested iteration controlled by k auto-limiting.
Space Complexity: O(1), absence of dynamically allocated accompanying supplemental storage.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
3022. Minimize OR of Remaining Elements Using Operations | Weekly Leetcode 382 • codingMohan • 2,698 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Minimize OR of Remaining Elements Using Operations easy or hard?
Minimize OR of Remaining Elements Using Operations Python/Java solution
How to solve Minimize OR of Remaining Elements Using Operations in O(n)?
What is the best approach for Minimize OR of Remaining Elements Using Operations?
Is Minimize OR of Remaining Elements Using Operations asked at Google/Amazon/Meta?
What data structure is used in Minimize OR of Remaining Elements Using Operations?
What is the time complexity of Minimize OR of Remaining Elements Using Operations?
Ready to solve this problem?
Practice Minimize OR of Remaining Elements Using Operations with our built-in code editor and test cases.
Practice on FleetCode