# Minimize OR of Remaining Elements Using Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-or-of-remaining-elements-using-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimize-or-of-remaining-elements-using-operations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Aon](https://scaleengineer.com/companies/aon)
---
## 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 <= 105`
* `0 <= nums[i] < 230`
* `0 <= k < nums.length`

# Approaches
## Bitwise Greedy with a Naive O(N^2) DP Check
This approach combines a greedy strategy on the bits of the result with a dynamic programming solution to a subproblem. The main idea is that to minimize a number, we should try to make its most significant bits zero. We iterate from the MSB downwards, deciding for each bit whether it can be zero in the final answer.

For each bit `b`, we test if it's possible to achieve a final OR value where bit `b` is 0, given the decisions we've made for higher bits. This check is formulated as a subproblem: can we partition the `nums` array into at least `n - k` contiguous groups, such that the bitwise AND of each group satisfies the bit constraints imposed by our target answer? 

A straightforward DP solves this subproblem in `O(N^2)`, leading to an overall complexity that is too slow but establishes a correct framework.
**Time:** O(B * N^2), where B is the number of bits (e.g., 30) and N is the length of `nums`. The outer loop runs B times, and the `check` function is O(N^2). · **Space:** O(N) for the DP array used within the `check` function.
**Pros:** The bitwise greedy strategy is a correct high-level approach for this type of problem.; It breaks down the problem into a more manageable subproblem.
**Cons:** The time complexity of `O(B * N^2)` is too high for the given constraints (`N` up to 10^5), and this solution will time out.
### Explanation
The algorithm determines the minimal OR value bit by bit. We start with a candidate answer of all ones and try to turn off each bit from 30 down to 0.

To check if a bit `b` can be zero, we call a function `check(target)`. This function must verify if we can partition `nums` into `m` groups (using `n-m` operations) such that `m >= n-k` and for each group `g_i`, `(AND of g_i) | target == target`. This is equivalent to finding the maximum number of valid groups we can form. 

We can find this maximum using dynamic programming. Let `dp[i]` be the maximum number of valid groups we can partition `nums[0...i-1]` into. The recurrence relation is:
`dp[i] = 1 + max(dp[j])` over all `0 <= j < i` such that `(nums[j] & ... & nums[i-1]) | target == target`.

This DP requires two nested loops to compute, resulting in an `O(N^2)` complexity for the `check` function. Since we call this for each bit, the total time complexity is `O(B * N^2)`, where `B` is the number of bits (around 30).

```java
class Solution {
    public int minimizeOrOfRemainingElements(int[] nums, int k) {
        int n = nums.length;
        int ans = -1; // Represents all bits set to 1

        for (int b = 29; b >= 0; b--) {
            int potentialAns = ans & ~(1 << b);
            if (isPossible(nums, k, potentialAns)) {
                ans = potentialAns;
            }
        }
        return ~ans;
    }

    private boolean isPossible(int[] nums, int k, int targetMask) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        // dp[i] = max number of valid groups in nums[0...i-1]
        // A group is valid if its AND result has 0s where targetMask has 1s.
        // (group_and & targetMask) == 0

        for (int i = 1; i <= n; i++) {
            dp[i] = -1; // Impossible
            int currentAnd = -1;
            for (int j = i - 1; j >= 0; j--) {
                currentAnd &= nums[j];
                if ((currentAnd & targetMask) == 0) {
                    if (dp[j] != -1) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        return dp[n] != -1 && n - dp[n] <= k;
    }
}
```
Note: The code uses a `targetMask` where set bits must be zero in the group ANDs. The final answer is `~ans` because `ans` stores this mask.
### Algorithm
- The core idea is to determine the bits of the minimum possible OR value one by one, from the most significant bit (MSB) to the least significant bit (LSB).
- We iterate from bit 29 down to 0. For each bit `b`, we try to make this bit 0 in our final answer. 
- Let `ans` be the minimum OR value we are building. Initially, `ans` is all ones. We try to turn off bit `b` in `ans`. Let this be `potential_ans = ans & ~(1 << b)`.
- We then check if it's possible to perform at most `k` operations such that the bitwise OR of the final array is at most `potential_ans`. This is equivalent to checking if for every element `y` in the final array, `y | potential_ans == potential_ans`.
- The `check(target)` function determines if this is possible. It does so by finding the maximum number of groups (`m_max`) we can partition `nums` into, where each group's bitwise AND is valid with respect to `target`. If `m_max >= nums.length - k`, the check passes.
- This version of `check` uses a dynamic programming approach. Let `dp[i]` be the maximum number of valid groups for the prefix `nums[0...i-1]`.
- The transition is `dp[i] = 1 + max(dp[j])` for all `0 <= j < i` where the subarray `nums[j...i-1]` forms a valid group (its AND is compatible with `target`).
- Calculating this DP naively takes `O(N^2)` time.

## Bitwise Greedy with an O(B*N) Check
This approach builds upon the previous one by optimizing the `check` function. The `O(N^2)` DP to find the maximum number of valid partitions is the bottleneck. We can optimize the DP transition from `O(N)` to `O(B)` by pre-calculating information about the positions of zeros for each bit.

Specifically, for each prefix of the array and for each bit, we find the last index where that bit was zero. This `last_zero` table allows us to quickly determine the valid range of starting points `j` for a group ending at `i-1`. This reduces the complexity of the `check` function to `O(B*N)`, making the overall solution `O(B^2 * N)`.
**Time:** O(B^2 * N). The main loop runs B times. The `check` function takes O(B*N) due to the inner loop to calculate `j_boundary` for each of the N elements. · **Space:** O(B*N) for the `last_zero` table.
**Pros:** Significantly faster than the naive `O(B*N^2)` approach.; The precomputation idea is a powerful technique for range-based problems.
**Cons:** The time complexity of `O(B^2 * N)` might still be too slow if `N` is large.; The space complexity of `O(B*N)` for the `last_zero` table can be large (e.g., `30 * 10^5 * 4` bytes ≈ 12 MB).
### Explanation
We keep the bitwise greedy framework but optimize the `check` function. The goal is to compute `dp[i] = 1 + max_{0 <= j <= J[i-1]} dp[j]` faster.

1.  **Precomputation**: We create a table `last_zero[i][b]` that stores the index of the most recent element `nums[p]` (with `p <= i`) where bit `b` is 0. This table can be filled in `O(B*N)` time.

2.  **Optimized `check` function**: Inside `check(target)`, for each `i` from 1 to `n`, we need to find the valid starting range for a group ending at `i-1`. A group `nums[j...i-1]` is valid if its AND is compatible with `target`. This means for every bit `b` that must be zero in the result, the subarray `nums[j...i-1]` must contain at least one number with bit `b` being zero. Using our `last_zero` table, this means `j` must be less than or equal to `last_zero[i-1][b]` for all such required zero bits `b`. 
    So, the latest possible start `j` is `J = min(last_zero[i-1][b])` over all required zero bits `b`. This takes `O(B)` time to compute for each `i`.

3.  **DP with Running Maximum**: The DP transition is now `dp[i] = 1 + max_dp[J]`, where `max_dp[J]` is the maximum value in `dp[0...J]`. We can maintain this `max_dp` array alongside the `dp` array. The `check` function now takes `O(B*N)`.

```java
class Solution {
    public int minimizeOrOfRemainingElements(int[] nums, int k) {
        int n = nums.length;
        int ans = -1; // All 1s

        // Precompute last_zero table
        int[][] last_zero = new int[n][30];
        for (int b = 0; b < 30; b++) {
            int last = -1;
            for (int i = 0; i < n; i++) {
                if (((nums[i] >> b) & 1) == 0) {
                    last = i;
                }
                last_zero[i][b] = last;
            }
        }

        for (int b = 29; b >= 0; b--) {
            int potentialAns = ans & ~(1 << b);
            if (isPossible(nums, k, potentialAns, last_zero)) {
                ans = potentialAns;
            }
        }
        return ~ans;
    }

    private boolean isPossible(int[] nums, int k, int targetMask, int[][] last_zero) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int[] max_dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int min_last = n;
            for (int b = 0; b < 30; b++) {
                if (((targetMask >> b) & 1) == 1) {
                    min_last = Math.min(min_last, last_zero[i - 1][b]);
                }
            }

            int j_boundary = min_last;
            if (j_boundary == -1) {
                dp[i] = -1; // Impossible to form a valid group ending at i-1
            } else {
                dp[i] = max_dp[j_boundary] + 1;
            }
            max_dp[i] = Math.max(max_dp[i - 1], dp[i]);
        }

        return max_dp[n] > 0 && n - max_dp[n] <= k;
    }
}
```
### Algorithm
- The overall bitwise greedy structure remains the same as the previous approach.
- The `check(target)` function is optimized. The key observation is that the `O(N^2)` DP can be sped up.
- The transition `dp[i] = 1 + max(dp[j])` for valid `j` can be optimized. A group `nums[j...i-1]` is valid if for every bit `b` that must be zero, there is at least one number in `nums[j...i-1]` with bit `b` being zero.
- We can precompute `last_zero[p][b]`, the index of the last number at or before `p` with bit `b` as zero. This takes `O(B*N)`.
- For a fixed `i` and `target`, the condition on `j` becomes `j <= min_{b | bit b must be 0} (last_zero[i-1][b])`. Let this boundary be `J`.
- The DP transition becomes `dp[i] = 1 + max(dp[0...J])`. We can maintain a running maximum of `dp` values to make this `O(1)`.
- Calculating `J` for each `i` takes `O(B)`. So the `check` function becomes `O(B*N)`.
- The precomputation of `last_zero` is done outside the main loop.

## Bitwise Greedy with a Fully Optimized O(N) Check
This is the most efficient approach, optimizing the `check` function's runtime from `O(B*N)` to `O(N)`. The total time complexity becomes `O(B*N)`.

The optimization comes from recognizing that the `j_boundary` array, which determines the DP transitions, doesn't need to be recomputed from scratch in every iteration of the main bitwise-greedy loop. As we decide on more bits to be zero in our answer, the constraints on partitions only get stricter. The `j_boundary` for a new mask can be calculated in `O(N)` from the `j_boundary` of the previous mask. This eliminates the `O(B)` factor from the `check` function, leading to a fully optimized solution.
**Time:** O(B*N), where B is the number of bits and N is the length of `nums`. Precomputation is `O(B*N)`, and the main loop runs B times with `O(N)` work inside. · **Space:** O(B*N) for the `last_zero` table. Additional `O(N)` space is used for DP arrays and boundary arrays.
**Pros:** This is the most efficient solution with optimal time complexity.; It correctly solves the problem within the given constraints.
**Cons:** The implementation is more complex, requiring careful state management across calls to the check function.; The `O(B*N)` space complexity might still be a concern for very large `N` on memory-constrained systems, though it's generally acceptable.
### Explanation
This approach optimizes the calculation of the `j_boundary` array across the main loop's iterations.

1.  **Precomputation**: We still precompute the `last_zero[i][b]` table in `O(B*N)` time.

2.  **Stateful Optimization**: We introduce an array `J_current` of size `n`. `J_current[i]` will store the `j_boundary` for `nums[0...i]` corresponding to the mask of the current best answer `ans`.

3.  **Main Loop**: We iterate from bit `b = 29` down to 0.
    a.  Create a temporary `J_test` array. For each `i` from 0 to `n-1`, calculate `J_test[i] = min(J_current[i], last_zero[i][b])`. This takes `O(N)`. This `J_test` array represents the boundaries if we were to add bit `b` to our set of required zero bits.
    b.  Call a modified `check` function that takes this precomputed `J_test` array as input. This `check` function now only needs to run the `O(N)` DP.
    c.  The DP is `dp[i] = 1 + max_dp[J_test[i-1]]`.
    d.  If `check` returns true, it means setting bit `b` to zero is possible. We update our answer `ans` and, crucially, update `J_current = J_test` to carry the tighter boundaries to the next iteration.

This way, each of the `B` iterations of the main loop takes `O(N)` time (for updating `J` and running the DP), making the total time complexity `O(B*N)`.

```java
class Solution {
    public int minimizeOrOfRemainingElements(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;

        int[][] last_zero = new int[n][30];
        for (int b = 0; b < 30; b++) {
            int last = -1;
            for (int i = 0; i < n; i++) {
                if (((nums[i] >> b) & 1) == 0) {
                    last = i;
                }
                last_zero[i][b] = last;
            }
        }

        int[] j_current = new int[n];
        for(int i=0; i<n; i++) j_current[i] = i; // Initially, no constraints

        for (int b = 29; b >= 0; b--) {
            int[] j_test = new int[n];
            for (int i = 0; i < n; i++) {
                j_test[i] = Math.min(j_current[i], last_zero[i][b]);
            }

            if (isPossible(n, k, j_test)) {
                // It's possible to make bit b zero, so we don't add it to ans.
                j_current = j_test;
            } else {
                // Must have bit b as 1.
                ans |= (1 << b);
            }
        }
        return ans;
    }

    private boolean isPossible(int n, int k, int[] j_boundaries) {
        int[] dp = new int[n + 1];
        int[] max_dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int boundary = j_boundaries[i - 1];
            if (boundary == -1) {
                dp[i] = -1; // Impossible
            } else {
                dp[i] = max_dp[boundary] + 1;
            }
            max_dp[i] = Math.max(max_dp[i - 1], dp[i]);
        }

        return max_dp[n] > 0 && n - max_dp[n] <= k;
    }
}
```
### Algorithm
- This approach refines the previous one to achieve the optimal time complexity.
- The bitwise greedy framework and the `last_zero` precomputation remain.
- The key insight is that when we go from checking bit `b` to bit `b-1`, the set of required zero bits only grows. The mask for bit `b` is `M_b`. The mask for `b-1` will be `M_{b-1} = M_b` or `M_{b-1} = M_b | (1 << (b-1))`.
- Let `J(i, mask)` be the `j_boundary` for index `i` and a given mask. We have `J(i, mask | (1 << b)) = min(J(i, mask), last_zero[i][b])`.
- Instead of recomputing the `j_boundary` array from scratch in `O(B*N)` inside each `check`, we can maintain a `J_current` array for the current best answer's mask.
- In each step of the main loop (for bit `b`), we compute a `J_test` array from `J_current` in `O(N)` time: `J_test[i] = min(J_current[i], last_zero[i][b])`.
- We then run the `O(N)` DP using this `J_test` array.
- If the check passes, we update `J_current = J_test` for the next iteration.

# Solutions
### Java

```java
class Solution {
public
  int minOrAfterOperations(int[] nums, int k) {
    int ans = 0, rans = 0;
    for (int i = 29; i >= 0; i--) {
      int test = ans + (1 << i);
      int cnt = 0;
      int val = 0;
      for (int num : 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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOrAfterOperations(vector<int> &nums, int k) {
    int ans = 0, rans = 0;
    for (int i = 29; i >= 0; i--) {
      int test = ans + (1 << i);
      int cnt = 0;
      int val = 0;
      for (auto it : nums) {
        if (val == 0) {
          val = test & it;
        } else {
          val &= test & it;
        }
        if (val) {
          cnt++;
        }
      }
      if (cnt > k) {
        rans += (1 << i);
      } else {
        ans += (1 << i);
      }
    }
    return rans;
  }
};

```

### Python

```python
class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int: ans = 0 rans = 0 for i in range(29, - 1, - 1): test = ans + (1 << i) cnt = 0 val = 0 for num in nums: if val == 0: val = test & num else: val &= test & num if val: cnt += 1 if cnt > k: rans += 1 << i else: ans += 1 << i return rans

```