[C++, Java, Python] Intuition with Explanation | Proof of Why? | Time: O(n)
Intuition\nMultiply by $2$ means left shift by $1$. We can left shift some numbers but at most $k$ times in total. To maximize the result we should generate set
# Intuition\nMultiply by $2$ means left shift by $1$. We can left shift some numbers but at most $k$ times in total. To maximize the result we should generate set bits in the most significant part of numbers.\n\nTake this array\n```\n 5 - 000000000101\n 6 - 000000000110\n 9 - 000000001001\n20 - 000000010100\n23 - 000000010111\n```\nTo maximize the result, we should pick the numbers having their Left Most Set Bit (LMSB) farthest among all elements. $20$ and $23$ have their LMSB maximum among all elements. We should try to shift $20$ or $23$, $k$ times combined. Like shift $20$ $x$ times and shift $23$ $k-x$ times.\n\n---\n\nBut still why is shifting only one number $k$ times is more optimal?\n- Suppose $k=5$ and we shifted $20$, $5$ times and LMSB went further $5$ steps on the left.\nThe modified array becomes:\n```\n  5 - 000000000101\n  6 - 000000000110\n  9 - 000000001001\n640 - 001010000000\n 23 - 000000010111\n```\nThe LMSB of $640$ is $2^9=512$ so Bitwise-OR of array will be atleast $2^9$. It can be more depending upon other less significant bits.\n`ans >= 001000000000 (512)`\n- Now let\'s say we don\'t give all $k$ moves to a single number. Since, we are not giving all $k$ moves to single number, we will never be able to generate $2^9$ set bit in any number. And even if somehow we generate all lower set bits $2^8, 2^7, 2^6, ...$ by distributing $k$ moves to different numbers, answer will still be less than $2^9$.\n$2^8 + 2^7 + 2^6 + ... + 2^0 = 2^9 - 1 < 2^9$\n\nTherefore, giving all $k$ moves to single element (that too having largest LMSB) is the most optimal.\n\n# Approach\n- Shift each number $k$ times and calculate Bitwise-OR.\n- To make this fast, pre-compute Bitwise-OR of elements before it (prefix) and after it (suffix).\n- Take maximum of them.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        int n = nums.size();\n        long long result = 0;\n        vector<int> prefix(n + 1), suffix(n + 1);\n        for (int i = 1; i < n; i++) {\n            prefix[i] = prefix[i - 1] | nums[i - 1];\n            suffix[n - i - 1] = suffix[n - i] | nums[n - i];\n        }\n        for (int i = 0; i < n; i++) {\n            result = max(result, prefix[i] | ((long long)nums[i] << k) | suffix[i]);\n        }\n        return result;\n    }\n};\n```\n```Java []\nclass Solution {\n    public long maximumOr(int[] nums, int k) {\n        int n = nums.length;\n        long result = 0;\n        int[] prefix = new int[n + 1];\n        int[] suffix = new int[n + 1];\n        for (int i = 1; i < n; i++) {\n            prefix[i] = prefix[i - 1] | nums[i - 1];\n            suffix[n - i - 1] = suffix[n - i] | nums[n - i];\n        }\n        for (int i = 0; i < n; i++) {\n            result = Math.max(result, prefix[i] | ((long)nums[i] << k) | suffix[i]);\n        }\n        return result;\n    }\n}\n```\n```Python []\nclass Solution:\n    def maximumOr(self, nums: List[int], k: int) -> int:\n        n, result = len(nums), 0\n        prefix, suffix = [0] * (n + 1), [0] * (n + 1)\n        for i in range(1, n):\n            prefix[i] = prefix[i - 1] | nums[i - 1]\n            suffix[n - i - 1] = suffix[n - i] | nums[n - i]\n        for i in range(n):\n            result = max(result, prefix[i] | (nums[i] << k) | suffix[i])\n        return result\n```\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$
['Bit Manipulation', 'Prefix Sum', 'C++', 'Java', 'Python3']