Maximum OR
Asked at Visa
Problem
Maximum OR lets you double elements of an array at most k times in total and asks for the largest possible bitwise OR of the whole array. The key observation is that all k doublings should go to a single element; then prefix and suffix ORs let you try every element in linear time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Doubling is a left shift. The highest bit of the final OR comes from whichever element is shifted furthest, so splitting shifts across elements can only lower the top bit.
Key insight: apply all k shifts to one element. Try every element as the chosen one.
For element i, the result is prefixOR[i-1] | (nums[i] << k) | suffixOR[i+1]. Precompute prefix and suffix ORs so each candidate is O(1).
Values reach 10^9 << 15, so use 64-bit integers.
Walkthrough: [12,9], k = 1: shift 12 -> 24 | 9 = 25; shift 9 -> 12 | 18 = 30. Answer 30.
Optimal Approach
Step 1: Build suffix[i] = nums[i] | nums[i+1] | ... with suffix[n] = 0.
Step 2: prefix = 0, best = 0.
Step 3: For each i: best = max(best, prefix | (nums[i] << k) | suffix[i+1]); prefix |= nums[i].
Step 4: Return best.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
Doubling the largest element. The best choice depends on which bits the other elements already provide — try them all.
Spreading doublings across several elements.
Recomputing the OR of the rest for each element — O(n²).
Shifting a 32-bit int in C++/Java; cast to 64-bit before shifting.
Solution Code
def maximumOr(nums, k):
n = len(nums)
suffix = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix[i] = suffix[i + 1] | nums[i]
prefix = best = 0
for i, x in enumerate(nums):
best = max(best, prefix | (x << k) | suffix[i + 1])
prefix |= x
return bestFrequently Asked Questions
What is the Maximum OR problem?
Maximum OR lets you double elements of an array at most `k` times in total and asks for the largest possible bitwise OR of the whole array. The key observation is that all `k` doublings should go to a single element; then prefix and suffix ORs let you try every element in linear time.
How do you solve Maximum OR?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum OR?
Maximum OR is asked at Visa. It is a medium difficulty problem.
What are common mistakes on Maximum OR?
- Doubling the largest element. The best choice depends on which bits the other elements already provide — try them all.
- Spreading doublings across several elements.
- Recomputing the OR of the rest for each element — `O(n²)`.
- Shifting a 32-bit int in C++/Java; cast to 64-bit before shifting.