2680. Maximum OR LeetCode Solution

In this guide, you will get 2680. Maximum OR LeetCode Solution with the best time and space complexity. The solution to Maximum OR problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum OR solution in C++
Maximum OR solution in Java
Maximum OR solution in Python
Additional Resources

2680. Maximum OR LeetCode Solution image

Problem Statement of Maximum OR

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 <= 105
1 <= nums[i] <= 109
1 <= k <= 15

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2680. Maximum OR LeetCode Solution in C++

class Solution {
 public:
  long long maximumOr(vector<int>& nums, int k) {
    const int n = nums.size();
    long ans = 0;
    // prefix[i] := nums[0] | nums[1] | ... | nums[i - 1]
    vector<long> prefix(n);
    // suffix[i] := nums[i + 1] | nums[i + 2] | ... nums[n - 1]
    vector<long> suffix(n);

    for (int i = 1; i < n; ++i)
      prefix[i] = prefix[i - 1] | nums[i - 1];

    for (int i = n - 2; i >= 0; --i)
      suffix[i] = suffix[i + 1] | nums[i + 1];

    // For each num, greedily shift it left by k bits.
    for (int i = 0; i < n; ++i)
      ans = max(ans, prefix[i] | static_cast<long>(nums[i]) << k | suffix[i]);

    return ans;
  }
};
/* code provided by PROGIEZ */

2680. Maximum OR LeetCode Solution in Java

class Solution {
  public long maximumOr(int[] nums, int k) {
    final int n = nums.length;
    long ans = 0;
    // prefix[i] := nums[0] | nums[1] | ... | nums[i - 1]
    long[] prefix = new long[n];
    // suffix[i] := nums[i + 1] | nums[i + 2] | ... nums[n - 1]
    long[] suffix = new long[n];

    for (int i = 1; i < n; ++i)
      prefix[i] = prefix[i - 1] | nums[i - 1];

    for (int i = n - 2; i >= 0; --i)
      suffix[i] = suffix[i + 1] | nums[i + 1];

    // For each num, greedily shift it left by k bits. The bitwise or value is
    // prefix[i] | nums[i] << k | suffix[i]
    for (int i = 0; i < n; ++i)
      ans = Math.max(ans, prefix[i] | (long) nums[i] << k | suffix[i]);

    return ans;
  }
}
// code provided by PROGIEZ

2680. Maximum OR LeetCode Solution in Python

class Solution:
  def maximumOr(self, nums: list[int], k: int) -> int:
    n = len(nums)
    # prefix[i] := nums[0] | nums[1] | ... | nums[i - 1]
    prefix = [0] * n
    # suffix[i] := nums[i + 1] | nums[i + 2] | ... nums[n - 1]
    suffix = [0] * n

    for i in range(1, n):
      prefix[i] = prefix[i - 1] | nums[i - 1]

    for i in range(n - 2, -1, -1):
      suffix[i] = suffix[i + 1] | nums[i + 1]

    # For each num, greedily shift it left by k bits.
    return max(p | num << k | s for num, p, s in zip(nums, prefix, suffix))
 # code by PROGIEZ