Rust/Python. Linear with full math proof (no handwaving, only math)
Math proof\n\nHere by the size of number I mean a lengh of its binary representation. For example 1011101 has size of 7.\n\nLets assume that we have an array of
# Math proof\n\nHere by the size of number I mean a lengh of its binary representation. For example `1011101` has size of `7`.\n\nLets assume that we have an array of numbers where one number has the size of `n` and all other numbers have the size of at most `n - 1`. And now we have `k` operations. Here I will prove that the best way to use them is to apply them all to the number of size `n`.\n\nTo prove this let\'s see \n 1. What is the minimum number we can achieve by applying k operations to max size number.\n 2. What is the maximum or of numbers we can achive by applying k to other numbers\n 3. Show that 1 > 2\n\n**1)** It will be $2^{n + k}$ (if we assume that our max-size number is one with all zeroes).\n**2)** We can see that the maximum will be achived if all other numbers consist of only ones. So `111..1` where the number of ones is `n-1` which is $2^{n} - 1$. No matter what we do, with our `k` operations we can\'t achieve the or of all numbers higher than $2^{n + k} - 1$\n**3)** So it is clear that 1 > 2 and therefore we proved that in this case we need to apply all operations to max-size value.\n\nNow lets assume that there are `x` elements of max-size and `y`  elements of of smaller size. It is easy to see that you should not use any operations on smaller size elements. This is because if you used even only one operation on smaller size element, you end up with `x+1` max-size elements and `y-1` smaller size elements but have left `k-1` operations.\n\nSo we end up with a situation where we have `k` operations and all number of the same size $n$ and need to decided how we should use those operations. And similar to beginning proof we can show that the minimum number that we can achieve by applying all operations to one number is $2^{n + k}$ and the maximum number in all other cases are $2^{n + k} - 1$\n\n\n\n# Solution\n\nSo we showed that we need to find which number we need to multiply by $2^k$ to get the maximum or. How can we efficiently do this? For example if we want to efficintly multiply k-th number.\n\n$A_0, ... A_{k-1}, A_k, A_{k+1}, ... A_n$\n\nThe answer will be `prefix_or[A[0..k-1]] | (A[k] * 2^k) | suffix_or[A[k+1..n]]`\n\nSo this can be done in $O(1)$ for every element, by precomputing `prefix_or` and `suffix_or`.\n\n# Complexity\n\nWe iterate over an array 3 times and use 2 additional arrays.\n\n- Time complexity: $O(n)$\n- Space complexity: $O(n)$\n\n# Code\n\n```Rust []\nimpl Solution {\n  pub fn maximum_or(nums: Vec<i32>, k: i32) -> i64 {\n    let (mult, n) = (1 << k as u64, nums.len());\n    let mut prefix_or = vec![0; n + 1];\n    for i in 0 .. n {\n      prefix_or[i + 1] = prefix_or[i] | nums[i] as u64;\n    }\n\n    let mut suffix_or = vec![0; n + 1];\n    for i in (0 .. n).rev() {\n      suffix_or[i] = suffix_or[i + 1] | nums[i] as u64;\n    }\n\n    let mut res = 0;\n    for i in 0 .. n {\n      res = res.max(prefix_or[i] | suffix_or[i + 1] | (nums[i] as u64 * mult));\n    }\n    return res as i64;\n  }\n}\n```\n```python []\nclass Solution:\n  def maximumOr(self, nums: List[int], k: int) -> int:\n    mult, n = 1 << k, len(nums)\n\n    prefix_or = [0] * (n + 1)\n    for i in range(n):\n      prefix_or[i + 1] = prefix_or[i] | nums[i]\n    \n    suffix_or = [0] * (n + 1)\n    for i in range(n - 1, -1, -1):\n      suffix_or[i] = suffix_or[i + 1] | nums[i]\n\n    res = 0\n    for i in range(n):\n      res = max(res, prefix_or[i] | suffix_or[i + 1] | (nums[i] * mult))\n    return res\n```\n
['Python', 'Rust']