Maximum OR

Medium
743.

Maximum OR

Maximum OR is a medium coding problem on arrays, greedy and bit manipulation, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumOr = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum OR — Solution in Python, Java & C++

Maximum OR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Maximum OR is a medium coding problem on arrays, greedy and bit manipulation, asked in Amazon, Google and Flipkart interviews.

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

Hints for Maximum OR

  1. Hint 1

    Spending all k doublings on a single element is always at least as good as splitting them.

  2. Hint 2

    So try each element as the one that gets all k doublings.

  3. Hint 3

    Prefix and suffix ORs let you evaluate each choice in constant time.

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

  1. Build pre[i], the OR of the first i elements, and suf[i], the OR of the elements from i onward.
  2. For each index i, the candidate is pre[i] | (nums[i] * 2^k) | suf[i+1].
  3. 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

Java

public static int maximumOr(int[] nums, int k) {
    int n = nums.length;
    int[] pre = new int[n + 1];
    int[] suf = new int[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];
    int best = 0;
    for (int i = 0; i < n; i++) {
        int cand = pre[i] | (nums[i] << k) | suf[i + 1];
        if (cand > best) best = cand;
    }
    return best;
}

C++

int maximumOr(vector<int>& nums, int k) {
    int n = (int) nums.size();
    vector<int> pre(n + 1, 0), suf(n + 1, 0);
    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];
    int best = 0;
    for (int i = 0; i < n; i++) {
        int cand = pre[i] | (nums[i] << k) | suf[i + 1];
        if (cand > best) best = cand;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms