Is Maximum OR easy or hard?

Maximum OR is rated Medium. The challenge is recognizing that applying all k operations to one element maximizes the shifted bits and that prefix/suffix OR preprocessing reduces the evaluation from O(n^2) to O(n).

Maximum OR Python/Java solution

Most implementations compute suffix OR values, then iterate while maintaining a prefix OR. For each index, evaluate (nums[i] << k) combined with prefix and suffix contributions. The same logic translates directly across Python, Java, C++, and JavaScript.

How to solve Maximum OR in O(n)?

Precompute a suffix OR array where suffix[i] stores the OR of elements from i to the end. Iterate through the array while maintaining a running prefix OR. For each index, compute (nums[i] << k) | prefix | suffix[i+1] and track the maximum result.

What is the best approach for Maximum OR?

The optimal approach uses prefix and suffix OR arrays with a greedy observation. Apply all k doubling operations to a single element by computing nums[i] << k, then combine it with the OR of elements before and after that index. This allows evaluating every candidate in O(n) time.

Is Maximum OR asked at Google/Amazon/Meta?

Bit manipulation and prefix OR optimization problems similar to Maximum OR appear in interviews at companies like Amazon and Google. They test understanding of bit operations, greedy reasoning, and efficient array preprocessing.

What data structure is used in Maximum OR?

The solution mainly uses arrays for prefix and suffix OR storage. Some implementations also use stacks to track intermediate OR states, but the core technique relies on bitwise operations and linear array traversal.

What is the time complexity of Maximum OR?

The optimized solution runs in O(n) time with O(n) extra space for suffix OR storage. Each element is processed once to build prefix and suffix OR values, and evaluating the shifted candidate takes constant time.

Description Hints 2 Solution Video 9:49

2680. Maximum OR

Q: How to solve Maximum OR in O(n)?

Precompute a suffix OR array where suffix[i] stores the OR of elements from i to the end. Iterate through the array while maintaining a running prefix OR. For each index, compute (nums[i] << k) | prefix | suffix[i+1] and track the maximum result.

Q: What is the best approach for Maximum OR?

The optimal approach uses prefix and suffix OR arrays with a greedy observation. Apply all k doubling operations to a single element by computing nums[i] << k, then combine it with the OR of elements before and after that index. This allows evaluating every candidate in O(n) time.

Q: Is Maximum OR asked at Google/Amazon/Meta?

Bit manipulation and prefix OR optimization problems similar to Maximum OR appear in interviews at companies like Amazon and Google. They test understanding of bit operations, greedy reasoning, and efficient array preprocessing.

Q: What data structure is used in Maximum OR?

The solution mainly uses arrays for prefix and suffix OR storage. Some implementations also use stacks to track intermediate OR states, but the core technique relies on bitwise operations and linear array traversal.

Q: What is the time complexity of Maximum OR?

The optimized solution runs in O(n) time with O(n) extra space for suffix OR storage. Each element is processed once to build prefix and suffix OR values, and evaluating the shifted candidate takes constant time.

Medium43.5% acceptance5 companies

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.

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⁵
1 <= nums[i] <= 10⁹
1 <= k <= 15

Asked at 5 companies

Point72 Visa

Infosys D. E. Shaw Microsoft

Topics

Hints open one at a time

Hint 1

The optimal solution should apply all the k operations on a single number.

Hint 2

Calculate the prefix or and the suffix or and perform k operations over each element, and maximize the answer.

9:49

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumOr(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[12,9]
1

Input

[8,1,2]
2

Your code is saved on this device.Solution