Minimize or of remaining elements using operations

Array Greedy Bit Manipulation

30.2% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_or_after_operations(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    // Try to zero out each bit from high to low
    // For each mask (bits we want to eliminate), check if we can do it in <= k ops
    let mut ans = 0i32;
    let mut mask = 0i32;
    for bit in (0..30).rev() {
      mask |= 1 << bit;
      // Count min ops to AND all consecutive groups to 0 under mask
      let mut ops = 0usize;
      let mut cur = !0i32;
      for &x in &nums {
        cur &= x & mask;
        if cur == 0 { ops += 1; cur = !0i32; }
      }
      // ops = number of groups that ANDed to 0. remaining elements = n - ops
      // If n - ops > 1 then those remaining are OR'd, we need to check.
      // Actually: if the total ops needed to collapse all into 0 is > k, can't clear this bit.
      // Ops needed: we want (n - ops) segments each with AND = 0 using k operations.
      // Each segment of length L needs L-1 operations to merge. Total = n - groups.
      // If we can get (n - ops_groups) remaining collapsed to 0 with k ops:
      let ops_needed = n - ops;
      if ops_needed > k { ans |= 1 << bit; mask ^= 1 << bit; }
    }
    ans
  }
}