# Maximum OR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-or)
Canonical: https://scaleengineer.com/dsa/problems/maximum-or
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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`

# Approaches
## Brute-Force Iteration
This approach iterates through each element of the array `nums`. For each element `nums[i]`, it calculates the potential maximum OR value that can be achieved if all `k` multiplication operations are applied to `nums[i]`. The overall maximum value across all choices of `i` is the answer.
**Time:** O(N^2), where N is the number of elements in `nums`. The outer loop runs N times, and for each iteration, the inner loop also runs N times to compute the total OR. · **Space:** O(1), as we only use a few variables to store the intermediate and final results, not dependent on the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The core idea is based on the observation that to maximize the bitwise OR, we should aim to set the most significant bits to 1. Applying `k` multiplications by 2 to a number `x` is equivalent to a left bit shift `x << k`, which is a very effective way to set higher-order bits. It is optimal to apply all `k` operations to a single element rather than distributing them. This brute-force approach directly implements this idea by trying every possible element `nums[i]` as the target for the `k` operations. For each choice of `nums[i]`, it computes the resulting total OR by iterating through the entire array again. While straightforward, this leads to a nested loop structure and quadratic time complexity.

```java
class Solution {
    public long maximumOr(int[] nums, int k) {
        long maxOrValue = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Apply k operations to nums[i]
            long shiftedNum = (long) nums[i] << k;
            
            // Calculate the OR with all other elements
            long currentOrValue = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    currentOrValue |= shiftedNum;
                } else {
                    currentOrValue |= nums[j];
                }
            }
            maxOrValue = Math.max(maxOrValue, currentOrValue);
        }
        return maxOrValue;
    }
}
```
### Algorithm
1. Initialize a variable `maxOrValue` to store the maximum OR value found so far, setting it to 0.
2. Iterate through each element `nums[i]` in the input array `nums` using an outer loop from `i = 0` to `n-1`.
3. For each `nums[i]`, this element is the candidate to apply all `k` operations on.
4. Calculate the value of `nums[i]` after `k` left shifts: `shiftedNum = (long)nums[i] << k`. Note the cast to `long` to prevent potential overflow.
5. Initialize a `currentOrValue` with `shiftedNum`.
6. Start an inner loop to iterate through all elements `nums[j]` from `j = 0` to `n-1`.
7. Inside the inner loop, if `j` is not equal to `i`, calculate the bitwise OR of `currentOrValue` with `nums[j]`: `currentOrValue |= nums[j]`.
8. After the inner loop completes, `currentOrValue` holds the total bitwise OR if `nums[i]` was the chosen element. Update the overall maximum: `maxOrValue = Math.max(maxOrValue, currentOrValue)`.
9. After the outer loop finishes, `maxOrValue` will contain the maximum possible OR value. Return `maxOrValue`.

## Optimized Approach with Prefix and Suffix ORs
This approach improves upon the brute-force method by precomputing prefix and suffix OR arrays. This allows us to calculate the bitwise OR of all elements *except* the current one in O(1) time, reducing the overall time complexity from O(N^2) to O(N).
**Time:** O(N), where N is the number of elements in `nums`. We perform three separate passes over the array (one for prefix ORs, one for suffix ORs, and one for the final calculation), each taking O(N) time. · **Space:** O(N), for the `prefixOr` and `suffixOr` arrays, each of size N.
**Pros:** Highly efficient with a linear time complexity, which is optimal.; Passes the given constraints with ease.
**Cons:** Requires extra space proportional to the input size for the prefix and suffix arrays.
### Explanation
The main bottleneck in the brute-force approach is the inner loop that recalculates the OR of all other elements. We can optimize this by precomputing the ORs. We use two auxiliary arrays: `prefixOr` and `suffixOr`.

- `prefixOr[i]` stores the bitwise OR of all elements from `nums[0]` to `nums[i]`.
- `suffixOr[i]` stores the bitwise OR of all elements from `nums[i]` to `nums[n-1]`.

Both these arrays can be computed in O(N) time. Once computed, for any index `i`, the OR of all elements *except* `nums[i]` is the OR of elements before it (`prefixOr[i-1]`) and elements after it (`suffixOr[i+1]`). This allows us to find the total OR for each choice of `i` in constant time inside a single loop, leading to a linear time solution.

```java
class Solution {
    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        
        long[] prefixOr = new long[n];
        prefixOr[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixOr[i] = prefixOr[i - 1] | nums[i];
        }

        long[] suffixOr = new long[n];
        suffixOr[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixOr[i] = suffixOr[i + 1] | nums[i];
        }

        long maxOrValue = 0;
        for (int i = 0; i < n; i++) {
            long shiftedNum = (long) nums[i] << k;
            
            long orOfOthers = 0;
            if (i > 0) {
                orOfOthers |= prefixOr[i - 1];
            }
            if (i < n - 1) {
                orOfOthers |= suffixOr[i + 1];
            }
            
            long currentOrValue = shiftedNum | orOfOthers;
            maxOrValue = Math.max(maxOrValue, currentOrValue);
        }

        return maxOrValue;
    }
}
```
### Algorithm
1. Handle the edge case where `n=1`. The result is simply `(long)nums[0] << k`.
2. Create a `prefixOr` array of size `n`. Compute it by iterating from left to right: `prefixOr[0] = nums[0]`, and `prefixOr[i] = prefixOr[i-1] | nums[i]` for `i > 0`.
3. Create a `suffixOr` array of size `n`. Compute it by iterating from right to left: `suffixOr[n-1] = nums[n-1]`, and `suffixOr[i] = suffixOr[i+1] | nums[i]` for `i < n-1`.
4. Initialize a variable `maxOrValue` to 0.
5. Iterate through the array from `i = 0` to `n-1`.
6. For each index `i`, calculate the bitwise OR of all other elements. This can be done in O(1) using the precomputed arrays:
   - The OR of elements before `i` is `prefixOr[i-1]` (or 0 if `i=0`).
   - The OR of elements after `i` is `suffixOr[i+1]` (or 0 if `i=n-1`).
   - `orOfOthers = (i > 0 ? prefixOr[i-1] : 0) | (i < n-1 ? suffixOr[i+1] : 0)`.
7. Calculate the total OR for the current choice: `currentOrValue = orOfOthers | ((long)nums[i] << k)`.
8. Update the maximum value: `maxOrValue = Math.max(maxOrValue, currentOrValue)`.
9. After the loop, return `maxOrValue`.

# Solutions
### Java

```java
class Solution { public long maximumOr ( int [] nums , int k ) { int n = nums . length ; long [] suf = new long [ n + 1 ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { suf [ i ] = suf [ i + 1 ] | nums [ i ]; } long ans = 0 , pre = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans = Math . max ( ans , pre | ( 1L * nums [ i ] << k ) | suf [ i + 1 ]); pre |= nums [ i ]; } return ans ; } }
```

### Python

```python
class Solution : def maximumOr ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) suf = [ 0 ] * ( n + 1 ) for i in range ( n - 1 , - 1 , - 1 ): suf [ i ] = suf [ i + 1 ] | nums [ i ] ans = pre = 0 for i , x in enumerate ( nums ): ans = max ( ans , pre | ( x << k ) | suf [ i + 1 ]) pre |= x return ans
```

### CPP

```cpp
class Solution { public: long long maximumOr ( vector < int >& nums , int k ) { int n = nums . size (); long long suf [ n + 1 ]; memset ( suf , 0 , sizeof ( suf )); for ( int i = n - 1 ; i >= 0 ; -- i ) { suf [ i ] = suf [ i + 1 ] | nums [ i ]; } long long ans = 0 , pre = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans = max ( ans , pre | ( 1LL * nums [ i ] << k ) | suf [ i + 1 ]); pre |= nums [ i ]; } return ans ; } };
```