---
# System prepended metadata

title: LC 2680. Maximum OR
tags: [medium, leedcode, Greedy, python]

---

# LC 2680. Maximum OR

### [Problem link](https://leetcode.com/problems/maximum-or/)

###### tags: `leedcode` `python` `medium` `Greedy`

You are given a  **0-indexed**  integer array <code>nums</code> of length <code>n</code> and an integer <code>k</code>. In an operation, you can choose an element and multiply it by <code>2</code>.

Return the maximum possible value of <code>nums[0] | nums[1] | ... | nums[n - 1]</code> that can be obtained after applying the operation on nums at most <code>k</code> times.

Note that <code>a | b</code> denotes the  **bitwise or**  between two integers <code>a</code> and <code>b</code>.

**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:** 

- <code>1 <= nums.length <= 10<sup>5</sup></code>
- <code>1 <= nums[i] <= 10<sup>9</sup></code>
- <code>1 <= k <= 15</code>


## Solution 1 - Greedy
```python=
class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        cnt = [0] * 32

        for num in nums:
            for i in range(len(cnt)):
                if (num >> i) & 1:
                    cnt[i] += 1

        res = 0
        for num in nums:
            tmp_cnt = cnt[:]
            for i in range(len(tmp_cnt)):
                if (num >> i) & 1:
                    tmp_cnt[i] -= 1

            tmp = 0
            for i in range(len(tmp_cnt)):
                if tmp_cnt[i] > 0:
                    tmp += (1 << i)

            tmp |= (num << k)
            res = max(res, tmp)

        return res
        
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(n)             |

## Note
計算總bit數後, 一個一個<<k試.

