# 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⁵</code>
- <code>1 <= nums[i] <= 10⁹</code>
- <code>1 <= k <= 15</code>

## Solution 1 - Greedy

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試.