Skip to main content

2680 - Maximum OR (Medium)

https://leetcode.com/problems/maximum-or/

Problem Statement

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 ofnums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at mostktimes.

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^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 15

Approach 1: Prefix & Suffix

Written by @wingkwong
class Solution:
def maximumOr(self, nums: List[int], k: int) -> int:
n, res = len(nums), 0
pre, suf = [0] * n, [0] * n
# calculate the prefix OR
for i in range(n - 1): pre[i + 1] = pre[i] | nums[i]
# calculate the suffix OR
for i in range(n - 1, 0, -1): suf[i - 1] = suf[i] | nums[i]
# iterate each number
# we apply k operations on nums[i], i.e. shift k bits to the left
# why not applying on multiple numbers?
# first in binary format, multiplying a number by 2 is shifting 1 bit to the left
# e.g. 0010 (2) -> 0100 (4)
# e.g. 0101 (5) -> 1010 (10)
# second, in OR operation, we wish there is a 1 as left as possible
# which produces the greater value
# hence, we apply on the same number to achieve the max value
# which produces the max OR value
# now we calculate nums[0] | nums[1] | ... | nums[n - 1]
# by utilising the prefix OR and suffix OR
# the reason is simple
# we precompute the result instead of calculate the OR values on each iteration
for i in range(n): res = max(res, pre[i] | nums[i] << k | suf[i])
return res