Maximum or

Array Greedy Bit Manipulation Prefix Sum

42.7% acceptance

Feb 25, 2026

423

You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2. Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times. Note that a | b denotes the bitwise or between two integers a and b.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_or(nums: Vec<i32>, k: i32) -> i64 {
    let n = nums.len();
    let mut prefix = vec![0i64; n + 1];
    let mut suffix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] | nums[i] as i64;
    }
    for i in (0..n).rev() {
      suffix[i] = suffix[i + 1] | nums[i] as i64;
    }
    let mut ans = 0i64;
    for i in 0..n {
      let val = prefix[i] | ((nums[i] as i64) << k) | suffix[i + 1];
      if val > ans { ans = val; }
    }
    ans
  }
}