O(n) with correctness proof
Math\nTricky part here is to prove that optimal solution consists of multiplying an input number by $2^k$. We prove the following lemma:\n\nLemma\nLet $x_{1},\l
## Math\nTricky part here is to prove that optimal solution consists of multiplying an input number by $2^k$. We prove the following lemma:\n\n**Lemma**\nLet $x_{1},\\ldots,x_{n}$ be natural numbers that require $l$ bits to represent in binary and let $k \\geq 1$. Then the following inequality is true:\n$$\n(2^{c_{1}}x_{1} | \\ldots |2^{c_{n}}x_{n}) \\leq max_{1 \\leq 1 \\leq n} (x_{1} | \\ldots | x_{i - 1} | x_{i} 2^{k} | x_{i + 1}| \\ldots |x_{n})\n$$\n\nwhere $c_{1} + \\ldots c_{n} = k$, $0 \\leq c_{i} \\leq k$.\n\n**Proof**\nLet $MSB(x)$ return the index of most significant set bit of $x$. Since $l$ bits is required for representing all $x_1, \\ldots, x_{n}$, we have $0 \\leq MSB(x_i) \\leq l - 1$. Let $j = max_{1 \\leq i \\leq n}MSB(x_{i})$ and let $MSB(x_{t}) = j$. Then $MSB(x_{t} * 2^k) = j + k$, and therefore $MSB(x_1 | \\ldots |x^t 2^k | \\ldots x_n) = j + k$, which means that $x_1 | \\ldots |x^t 2^k | \\ldots x_n \\geq 2^{j + k}$ (1).\n\nNow consider $x_{1}2^{c_1} | \\ldots | x_{n}2^{c_n}$, $c_1 + \\ldots + c_n = k, c_i \\geq 0, c_i < k$. Since all $c_{i} \\leq k - 1$, it is evident that $MSB(x_{1}2^{c_1} | \\ldots | x_{n}2^{c_n}) \\leq j + k - 1$. In best case scenario, all bits preceding $j + k - 1$ are 1 as well, which means that largest possible value for $x_{1}2^{c_1} | \\ldots | x_{n}2^{c_n}$ under previous constraints is:\n$$\n2^{k - 1} \\sum_{i=0}^{j}2^i = 2^{k - 1} (2^{j + 1} - 1) = 2^{k + j} - 2^{k - 1} < 2^{k + j} (2)\n$$\n\nFrom inequalities (1) and (2), we deduce that the largest achiveable value of $$x_{1}2^{c_1} | \\ldots | x_{n}2^{c_n}$$ when not multiplying any $x_i$ by $2^k$ is strictly less than minimum value of $x_{1}2^{c_1} | \\ldots | x_{n}^2{c_n}$ when $x_t$ is multiplied by $2^k$, which concludes the proof.\n\n## Code\nInstead of computing MSB as presented in previous proof, we just try every $x_{i}$ as candidate by multiplying it with $2^k$ (which is equivalent to left shifting $x_i$ k times). Alternatively, one could maximize $MSB$ over the input array and then try each number that has maximum MSB, but this approach would require an additional iteration over the input array.\n\n To include the rest of the input, we precompute all Bitwise OR prefixes and suffixes. For $nums[i]$, we compute $prefix[i - 1]$ |$nums[i] 2^{k}$ | $suffix[i + 1]$, with edge cases being $i = 0, i = n - 1$. This approach leads to an $O(n)$ solution, if $1 << k$ is considered an $O(1)$ operation. Memory requirement is $O(n)$, as we need two arrays of size $n$ for prefix and suffix computation.\n\n```\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<long long> prefix(n);\n        vector<long long> suffix(n);\n\n        prefix[0] = nums[0];\n        suffix[n - 1] = nums[n - 1];\n\n        for(int i = 1; i < n; i++) {\n            prefix[i] = prefix[i - 1] | nums[i];\n            suffix[n - i - 1] = suffix[n - i] | nums[n - i - 1];\n        }\n\n        long long ans = 0;\n        long long tmp, p, s;\n        long long c = 1 << k;\n        for(int i = 0; i < n; i++) {\n            tmp = nums[i] * c;\n            p = i > 0 ? prefix[i - 1] : 0;\n            s = i < n - 1 ? suffix[i + 1] : 0;\n            ans = max(ans, p | tmp | s);\n        }\n\n        return ans;\n    }\n};\n```
['Math', 'C++']