2680

2680. Maximum OR (Medium)

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

Related Topics:
Array, Greedy, Bit Manipulation, Prefix Sum

Hints:

• The optimal solution should apply all the k operations on a single number.
• Calculate the prefix or and the suffix or and perform k operations over each element, and maximize the answer.

Solution 1.

1. The optimal solution should apply all the k operations on a single number.
2. Calculate the prefix or and the suffix or and perform k operations over each element, and maximize the answer.

Proof of point 1:

We know that we should greedily pick some numbers whose highest bits are as high as possible and shift them. If there are multiple numbers having the same highest bit, and we moved one of them. Which number we should move in the next round? Must be this number that we just moved.

// OJ: https://leetcode.com/problems/maximum-or
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long maximumOr(vector<int>& A, int K) {
        long long N = A.size(), ans = 0, pre = 0;
        vector<long long> suf(N + 1);
        for (int i = N - 1; i >= 0; --i) suf[i] = suf[i + 1] | A[i];
        for (int i = 0; i < N; ++i) {
            ans = max(ans, pre | suf[i + 1] | ((long long)A[i] << K));
            pre |= A[i];
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/maximum-or
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    long long maximumOr(vector<int>& A, int k) {
        long long cnt[32] = {}, all = 0, ans = 0;
        for (int n : A) {
            for (int i = 0; i < 32; ++i) cnt[i] += (n >> i & 1);
            all |= n;
        }
        for (int n : A) {
            int other = 0;
            for (int i = 0; i < 32; ++i) {
                if (cnt[i] - (n >> i & 1) > 0) other |= (1 << i);
            }
            ans = max(ans, other | ((long long)n << k));
        }
        return ans;
    }
};