Input: nums =[12,9], k =1Output: 30Explanation: 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 is30.
Input: nums =[8,1,2], k =2Output: 35Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return32|1|2=35.
To maximize the OR after multiplying an element by 2 up to k times, we should try all possibilities of applying all k operations to each element. For each element, we can multiply it by 2^k and OR it with the rest of the array (excluding the current element). Precomputing prefix and suffix ORs allows us to do this efficiently.
classSolution {
public:longlong maximumOr(vector<int>& nums, int k) {
int n = nums.size();
vector<longlong> pre(n+1), suf(n+1);
for (int i =0; i < n; ++i) pre[i+1] = pre[i] | nums[i];
for (int i = n-1; i >=0; --i) suf[i] = suf[i+1] | nums[i];
longlong ans =0;
for (int i =0; i < n; ++i) {
longlong cur = pre[i] | (1LL* nums[i] << k) | suf[i+1];
ans = max(ans, cur);
}
return ans;
}
};
classSolution {
publiclongmaximumOr(int[] nums, int k) {
int n = nums.length;
long[] pre =newlong[n+1], suf =newlong[n+1];
for (int i = 0; i < n; i++) pre[i+1]= pre[i]| nums[i];
for (int i = n-1; i >= 0; i--) suf[i]= suf[i+1]| nums[i];
long ans = 0;
for (int i = 0; i < n; i++) {
long cur = pre[i]| ((long)nums[i]<< k) | suf[i+1];
ans = Math.max(ans, cur);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
funmaximumOr(nums: IntArray, k: Int): Long {
val n = nums.size
val pre = LongArray(n+1)
val suf = LongArray(n+1)
for (i in0 until n) pre[i+1] = pre[i] or nums[i].toLong()
for (i in n-1 downTo 0) suf[i] = suf[i+1] or nums[i].toLong()
var ans = 0Lfor (i in0 until n) {
val cur = pre[i] or (nums[i].toLong() shl k) or suf[i+1]
ans = maxOf(ans, cur)
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
defmaximumOr(self, nums: list[int], k: int) -> int:
n = len(nums)
pre = [0] * (n +1)
suf = [0] * (n +1)
for i in range(n):
pre[i+1] = pre[i] | nums[i]
for i in range(n-1, -1, -1):
suf[i] = suf[i+1] | nums[i]
ans =0for i in range(n):
cur = pre[i] | (nums[i] << k) | suf[i+1]
ans = max(ans, cur)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
pubfnmaximum_or(nums: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
letmut pre =vec![0i64; n+1];
letmut suf =vec![0i64; n+1];
for i in0..n {
pre[i+1] = pre[i] | nums[i] asi64;
}
for i in (0..n).rev() {
suf[i] = suf[i+1] | nums[i] asi64;
}
letmut ans =0i64;
for i in0..n {
let cur = pre[i] | ((nums[i] asi64) << k) | suf[i+1];
ans = ans.max(cur);
}
ans
}
}