MediumArrayGreedyBit ManipulationPrefix SumUpdated Sep 2026

2680. Maximum OR

Asked at Visa

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You get an integer array nums and a number k. You may perform an operation at most k times. One operation picks any element of the array and doubles it (multiplies it by 2). You can pick the same element many times, or spread the operations over different elements.

After you finish, take the bitwise OR of all elements: nums[0] | nums[1] | ... | nums[n-1]. Return the largest OR value you can reach.

Doubling a number is the same as shifting its bits one place to the left. So each operation moves an element's bits up by one position, which can light up higher bits in the final OR.

Doubling pushes bits left

nums12901k = 1: we may double one element, here index 1after1218019 doubled to 18, and 12 | 18 = 30
Each operation shifts one element's bits one step left, so the OR can gain higher bits.

Constraints

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

Examples

Example 1
Inputnums = [12,9], k = 1
Output30
WhyDouble 9 once to get 18. Now the array is [12,18], and 12 | 18 = 30. Doubling 12 instead gives 24 | 9 = 25, which is smaller, so 30 is the best.
Example 2
Inputnums = [8,1,2], k = 2
Output35
WhyUse both operations on 8: 8 becomes 32. Then 32 | 1 | 2 = 35. Spreading the two doublings (for example 16 | 2 | 2) gives a smaller OR.

Asked At

1 companies
CompanyDifficulty
VisaMediumView all Visa questions →

How to Think About It

1

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.

2

Key insight: apply all k shifts to one element. Try every element as the chosen one.

3

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).

4

Values reach 10^9 << 15, so use 64-bit integers.

5

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).

All k shifts on one element

numssuffix OR = 912901Try index 0: prefix is empty, suffix after it is 9candidate = prefix | (nums[i] << k) | suffix[i+1]i=0: 0 | (12<<1) | 9 = 24 | 9 = 25i=1: 12 | (9<<1) | 0 = 12 | 18 = 30build suffix ORs from the rightsweep left, keep prefix ORbest = max(best, prefix | (x << k) | suffix[Prefix and suffix ORs make each candidate O(1), so thewhole scan is linear.
Putting every shift on a single element raises its top bit the most, so we try each element as that one.
ComplexityTime O(n)Space O(n)One pass builds the suffix ORs, a second pass tests every element as the shifted one; the O(n) space holds the suffix array.

What Trips People Up in Real Interviews

1

Doubling the largest element. The best choice depends on which bits the other elements already provide — try them all.

2

Spreading doublings across several elements.

3

Recomputing the OR of the rest for each element — O(n²).

4

Shifting a 32-bit int in C++/Java; cast to 64-bit before shifting.

Solution Code

O(n) time
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 best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.