Maximum OR — Medium Problem & Solution

You may apply at most k operations; each doubles one element of nums. The same element may be doubled more than once.

Difficulty: Medium
Topics: Arrays, Greedy, Bit Manipulation, Prefix Sum
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may apply at most k operations; each doubles one element of nums. The same element may be doubled more than once.

Return the maximum possible bitwise OR of the final array.

Example 1

Input: nums = [12,9], k = 1
Output: 30
Explanation: Doubling 9 to 18 gives 12 OR 18 = 30.

Example 2

Input: nums = [8,1,2], k = 2
Output: 35
Explanation: Doubling 8 twice gives 32, and 32 OR 1 OR 2 = 35.

Example 3

Input: nums = [7], k = 0
Output: 7

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
0 <= k <= 5

How to solve Maximum OR

Concentrating the budget is optimal, so there are only n candidates. Prefix and suffix ORs make each candidate a constant-time expression.

Approach

Build pre[i], the OR of the first i elements, and suf[i], the OR of the elements from i onward.
For each index i, the candidate is pre[i] | (nums[i] * 2^k) | suf[i+1].
Return the largest candidate.

Why it works

Doubling shifts an element's bits left. Splitting the budget across two elements shifts each less far, and the highest bit reachable — which dominates the OR — is maximised by giving every doubling to one element. Since the best element is not known in advance, all n are tried.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Splitting the doublings between elements can only lower the top bit reached.
Recomputing the OR of the other elements per candidate is O(n²); the prefix and suffix arrays remove that.
At LeetCode's real limits the answer needs 64 bits; this version caps the values so it fits in int.

Reference solution

Python

from typing import List

def maximumOr(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]
    best = 0
    for i in range(n):
        best = max(best, pre[i] | (nums[i] << k) | suf[i + 1])
    return best

JavaScript

var maximumOr = function(nums, k) {
    var n = nums.length;
    var pre = [], suf = [];
    for (var t = 0; t <= n; t++) { pre.push(0); suf.push(0); }
    for (var i = 0; i < n; i++) pre[i + 1] = pre[i] | nums[i];
    for (var j = n - 1; j >= 0; j--) suf[j] = suf[j + 1] | nums[j];
    var best = 0;
    for (var m = 0; m < n; m++) {
        var cand = pre[m] | (nums[m] * Math.pow(2, k)) | suf[m + 1];
        if (cand > best) best = cand;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue