Scale Engineer

Minimize OR of Remaining Elements Using Operations

Hard
#2690Time: 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.1 company
Patterns
GreedyBit Manipulation
Data structures
Array
Companies
Aon

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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).

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.

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem