problemmediumalgorithmsleetcode-2680leetcode 2680leetcode2680

Maximum OR

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 ofnums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at mostk times.

Note that a | b denotes the bitwise or between two integers a and b.

Examples

Example 1

Input: nums = [12,9], k = 1
Output: 30
Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.

Example 2

Input: nums = [8,1,2], k = 2
Output: 35
Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 15

Solution

Method 1 – Bit Manipulation with Prefix/Suffix OR

Intuition

To maximize the OR after multiplying an element by 2 up to k times, we should try all possibilities of applying all k operations to each element. For each element, we can multiply it by 2^k and OR it with the rest of the array (excluding the current element). Precomputing prefix and suffix ORs allows us to do this efficiently.

Approach

  1. Precompute prefix OR and suffix OR arrays for the input.
  2. For each index, calculate the OR of all elements except the current one using prefix and suffix ORs.
  3. For each index, compute the value if we multiply nums[i] by 2^k and OR it with the rest.
  4. Track the maximum value found.
  5. Return the maximum.

Code

C++
class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> pre(n+1), suf(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] | nums[i];
        for (int i = n-1; i >= 0; --i) suf[i] = suf[i+1] | nums[i];
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            long long cur = pre[i] | (1LL * nums[i] << k) | suf[i+1];
            ans = max(ans, cur);
        }
        return ans;
    }
};
Go
func maximumOr(nums []int, k int) int64 {
    n := len(nums)
    pre := make([]int64, n+1)
    suf := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] | int64(nums[i])
    }
    for i := n-1; i >= 0; i-- {
        suf[i] = suf[i+1] | int64(nums[i])
    }
    ans := int64(0)
    for i := 0; i < n; i++ {
        cur := pre[i] | (int64(nums[i]) << k) | suf[i+1]
        if cur > ans {
            ans = cur
        }
    }
    return ans
}
Java
class Solution {
    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n+1], suf = new long[n+1];
        for (int i = 0; i < n; i++) pre[i+1] = pre[i] | nums[i];
        for (int i = n-1; i >= 0; i--) suf[i] = suf[i+1] | nums[i];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long cur = pre[i] | ((long)nums[i] << k) | suf[i+1];
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        val pre = LongArray(n+1)
        val suf = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] or nums[i].toLong()
        for (i in n-1 downTo 0) suf[i] = suf[i+1] or nums[i].toLong()
        var ans = 0L
        for (i in 0 until n) {
            val cur = pre[i] or (nums[i].toLong() shl k) or suf[i+1]
            ans = maxOf(ans, cur)
        }
        return ans
    }
}
Python
class Solution:
    def maximumOr(self, nums: list[int], k: int) -> int:
        n = len(nums)
        pre = [0] * (n + 1)
        suf = [0] * (n + 1)
        for i in range(n):
            pre[i+1] = pre[i] | nums[i]
        for i in range(n-1, -1, -1):
            suf[i] = suf[i+1] | nums[i]
        ans = 0
        for i in range(n):
            cur = pre[i] | (nums[i] << k) | suf[i+1]
            ans = max(ans, cur)
        return ans
Rust
impl Solution {
    pub fn maximum_or(nums: Vec<i32>, k: i32) -> i64 {
        let n = nums.len();
        let mut pre = vec![0i64; n+1];
        let mut suf = vec![0i64; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] | nums[i] as i64;
        }
        for i in (0..n).rev() {
            suf[i] = suf[i+1] | nums[i] as i64;
        }
        let mut ans = 0i64;
        for i in 0..n {
            let cur = pre[i] | ((nums[i] as i64) << k) | suf[i+1];
            ans = ans.max(cur);
        }
        ans
    }
}
TypeScript
class Solution {
    maximumOr(nums: number[], k: number): number {
        const n = nums.length;
        const pre = new Array(n+1).fill(0);
        const suf = new Array(n+1).fill(0);
        for (let i = 0; i < n; i++) pre[i+1] = pre[i] | nums[i];
        for (let i = n-1; i >= 0; i--) suf[i] = suf[i+1] | nums[i];
        let ans = 0;
        for (let i = 0; i < n; i++) {
            const cur = pre[i] | (nums[i] << k) | suf[i+1];
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array three times.
  • 🧺 Space complexity: O(n) — For prefix and suffix arrays.

Comments