Minimize OR of Remaining Elements Using Operations solution and explanation
4 more videos on this problem
3022. Minimize OR of Remaining Elements Using Operations | Weekly Leetcode 382codingMohan · 50:08 · 2K views
3022. Minimize OR of Remaining Elements Using Operations (Leetcode Hard)Programming Live with Larry · 2:39:22 · 731 views
【每日一题】LeetCode 3022. Minimize OR of Remaining Elements Using OperationsHuifeng Guan · 48:41 · 388 views
Minimize OR of Remaining Elements Using Operations| LeetCode weekly contest 382| Problem 3022CoWo (Code World) · 14:17 · 357 views
[LC-WC-382] Minimize OR of Remaining Elements Using OperationsBeing Zero · 32:09 · 143 views
The problem
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.
def minimize_or(nums, k):
result = 0
for i in range(len(nums)):
if i < len(nums) - 1 and k > 0:
nums[i + 1] = nums[i] & nums[i + 1]
k -= 1
for num in nums:
result |= num
return result
if __name__ == '__main__':
nums = [3, 5, 3, 2, 7]
k = 2
print(minimize_or(nums, k))public class MinimizeOR {
public static int minimizeOR(int[] nums, int k) {
int result = 0;
for (int i = 0; i < nums.length && k > 0; i++) {
if (i < nums.length - 1) {
nums[i + 1] = nums[i] & nums[i + 1];
k--;
}
}
for (int num : nums) {
result |= num;
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 5, 3, 2, 7};
int k = 2;
System.out.println(minimizeOR(nums, k));
}
}#include <vector>
#include <iostream>
int minimizeOR(std::vector<int>& nums, int k) {
int result = 0;
for (int i = 0; i < nums.size() && k > 0; ++i) {
if (i < nums.size() - 1) {
nums[i+1] &= nums[i];
--k;
}
}
for (int num : nums)
result |= num;
return result;
}
int main() {
std::vector<int> nums = {3, 5, 3, 2, 7};
int k = 2;
std::cout << minimizeOR(nums, k) << std::endl;
return 0;
}function minimizeOR(nums, k) {
let result = 0;
for (let i = 0; i < nums.length && k > 0; i++) {
if (i < nums.length - 1) {
nums[i+1] = nums[i] & nums[i+1];
k--;
}
}
for (const num of nums) {
result |= num;
}
return result;
}
const nums = [3, 5, 3, 2, 7];
const k = 2;
console.log(minimizeOR(nums, k));#include <stdio.h>
int minimizeOR(int* nums, int numsSize, int k) {
int result = 0;
for (int i = 0; i < numsSize && k > 0; i++) {
if (i < numsSize - 1) {
nums[i + 1] = nums[i] & nums[i + 1];
k--;
}
else
break;
}
for (int i = 0; i < numsSize; i++)
result |= nums[i];
return result;
}
int main() {
int nums[] = {3, 5, 3, 2, 7};
int k = 2;
printf("%d\n", minimizeOR(nums, 5, k));
return 0;
}using System;
public class MinimizeOr
{
public static int MinimizeOR(int[] nums, int k)
{
int result = 0;
for (int i = 0; i < nums.Length && k > 0; i++)
{
if (i < nums.Length - 1) {
nums[i + 1] = nums[i] & nums[i + 1];
k--;
}
}
foreach (int num in nums)
result |= num;
return result;
}
public static void Main(string[] args)
{
int[] nums = { 3, 5, 3, 2, 7 };
int k = 2;
Console.WriteLine(MinimizeOR(nums, k));
}
}Python facilitates easy syntax for merging elements by bitwise logical conjunction as k permits.
Time Complexity: O(n).
Space Complexity: O(1) due to inline alteration.
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.
def minimize_optimally(nums, k):
min_value = float('inf')
n = len(nums)
for i in range(min(k + 1, n)):
current_min = nums[i]
for j in range(i, n):
current_min &= nums[j]
if j - i + 1 <= k:
min_value = min(min_value, current_min)
return min_value
if __name__ == '__main__':
nums = [3, 5, 3, 2, 7]
k = 2
print(minimize_optimally(nums, k))import java.util.Arrays;
public class MinimizeOptimally {
public static int minimizeOptimally(int[] nums, int k) {
int min = Integer.MAX_VALUE;
for (int i = 0; i <= k && i < nums.length; i++) {
int localMin = nums[i];
for (int j = i; j < nums.length; j++) {
localMin &= nums[j];
if (j - i + 1 <= k) {
min = Math.min(min, localMin);
}
}
}
return min;
}
public static void main(String[] args) {
int[] nums = {3, 5, 3, 2, 7};
int k = 2;
System.out.println(minimizeOptimally(nums, k));
}
}#include <iostream>
#include <vector>
int minimizeOptimally(std::vector<int>& nums, int k) {
int min = INT_MAX;
int n = nums.size();
for (int i = 0; i <= k && i < n; ++i) {
int localMin = nums[i];
for (int j = i; j < n; ++j) {
localMin &= nums[j];
if (j - i + 1 <= k)
min = std::min(min, localMin);
}
}
return min;
}
int main() {
std::vector<int> nums = {3, 5, 3, 2, 7};
int k = 2;
std::cout << minimizeOptimally(nums, k) << std::endl;
return 0;
}function minimizeOptimally(nums, k) {
let minValue = Number.MAX_SAFE_INTEGER;
for (let i = 0; i <= k && i < nums.length; i++) {
let currentMin = nums[i];
for (let j = i; j < nums.length; j++) {
currentMin &= nums[j];
if (j - i + 1 <= k) {
minValue = Math.min(minValue, currentMin);
}
}
}
return minValue;
}
const nums = [3, 5, 3, 2, 7];
const k = 2;
console.log(minimizeOptimally(nums, k));#include <stdio.h>
int minimizeOptimally(int* nums, int numsSize, int k) {
int min = 2147483647;
for (int i = 0; i <= k; i++) {
int localMin = nums[i];
for (int j = i; j < numsSize; j++) {
localMin &= nums[j];
if (j - i + 1 <= k)
min = (min < localMin) ? min : localMin;
}
}
return min;
}
int main() {
int nums[] = {3, 5, 3, 2, 7};
int k = 2;
printf("%d\n", minimizeOptimally(nums, 5, k));
return 0;
}using System;
public class MinimizeOptimally {
public static int MinimizeOptimally(int[] nums, int k) {
int min = int.MaxValue;
int len = nums.Length;
for (int i = 0; i <= k && i < len; i++) {
int localMin = nums[i];
for (int j = i; j < len; j++) {
localMin &= nums[j];
if (j - i + 1 <= k) {
min = Math.Min(min, localMin);
}
}
}
return min;
}
public static void Main(string[] args) {
int[] nums = { 3, 5, 3, 2, 7 };
int k = 2;
Console.WriteLine(MinimizeOptimally(nums, k));
}
}Python facilitates high simplicity utilization within loops dynamically modifying condition diversity provision.
Time Complexity: O(n * k), containing redundancy adaptive leaflet partitions.
Space Complexity: O(1).
Approach 3: Default Approach
func minOrAfterOperations(nums []int, k int) int {
ans := 0
rans := 0
for i := 29; i >= 0; i-- {
test := ans + (1 << i)
cnt := 0
val := 0
for _, num := range nums {
if val == 0 {
val = test & num
} else {
val &= test & num
}
if val != 0 {
cnt++
}
}
if cnt > k {
rans += (1 << i)
} else {
ans += (1 << i)
}
}
return rans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach based on AND and OR operations | Time Complexity: O(n). |
| Optimize by Pairing Strategically | Time Complexity: O(n * k), containing redundancy adaptive leaflet partitions. |
| Default Approach | – |
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. |
Frequently asked questions
Is Minimize OR of Remaining Elements Using Operations easy or hard?
The problem is rated Hard because it requires combining greedy reasoning with bit manipulation and a feasibility check. Understanding that AND operations only remove bits while OR aggregates them is the key insight needed to design the optimal algorithm.
Minimize OR of Remaining Elements Using Operations Python/Java solution
Implement the greedy bit-check approach. Iterate bits from high to low, assume the bit is removable, then scan the array while building AND segments. If more than k merges are required, the bit must be present in the final OR. The same logic works in Python, Java, C++, C#, and JavaScript.
How to solve Minimize OR of Remaining Elements Using Operations in O(n)?
Pure O(n) is not typical because each bit of the result must be validated. However, the practical optimal solution is O(n log M). For each candidate bit, you simulate merges with a single pass through the array and track segment AND values to determine whether the bit can be removed.
What is the best approach for Minimize OR of Remaining Elements Using Operations?
The most effective approach uses greedy bit manipulation. Iterate bits from most significant to least significant and check if that bit can be eliminated from the final OR by merging adjacent elements using AND operations. A linear scan verifies whether the required merges stay within k. This produces the minimum OR value in O(n log M) time where M is the maximum element value.
Is Minimize OR of Remaining Elements Using Operations asked at Google/Amazon/Meta?
Problems combining greedy decisions with bit manipulation are common in interviews at companies like Google, Amazon, and Meta. Variants involving minimizing OR or maximizing AND frequently appear because they test understanding of bitwise properties and greedy feasibility checks.
What data structure is used in Minimize OR of Remaining Elements Using Operations?
The problem mainly relies on arrays and bitwise operations. No complex data structures are required. The algorithm scans the array while maintaining a running AND value and counting merges needed to satisfy the bit constraints.
What is the time complexity of Minimize OR of Remaining Elements Using Operations?
The optimal solution runs in O(n log M) time and O(1) space. The algorithm checks each bit of the result (up to ~30 for typical integer constraints) and performs a linear scan of the array to verify feasibility using greedy AND merging.