O(1) space: keep track of bits, super simple to understand and detailed explanation
Glossary:\n- bit set: ith bit is set means the ith bit equals one \n- highest bit of a number: highest i for which the ith bit is set (eg. in 1001 the highest b
Glossary:\n- *bit set*: ith bit is set means the ith bit equals one \n- *highest bit of a number*: highest `i` for which the ith bit is set (eg. in 1001 the highest bit is the 4th bit)\n- *the OR* :  `nums[0] | nums[1] | ... | nums[n - 1]`, after one operation (not necessarily the final result)\n\n\nExplanation\n\n1. When you do `nums[0] | nums[1] | ... | nums[n - 1]`, what you get as a result is a number which will have the `i`th bit set if any of `nums[i]` has this bit set.\n2. We want to maximise the result. What does it mean? It means that we want to have all the higher bits as high as possible. So any solution that maximizes the higher bits will find the solution.\n3. From point 2. **we can deduce what we need to multiply only one number `k` times**. Why?\n     1.  Lets say bit `b` is the highest bit of all the numbers in `nums`.\n     2.  Let\'s say we picked a number (let\'s call it `x`) from nums that has this highest bit and applied the first operation on it\n     3.  This means that now the OR will have the highest bit = `b+1` \n     4.  For the next operation, we have to to chose `x` again. Why? Because if we chose `x` again then the OR will have  `b+2` as the highest bit and it\'s impossible have a higher OR by chosing another number than `x` (since the highest bit is `b` if you chose another one the OR will have max `b+1` as the highest bit)\n     5.  Repeat the same logic `k` times\n\n4. Now that we deduced that we just have to pick one number and double it `k` times, the question becomes way easier. You simply have to **iterate through all numbers and chose the one for which the answer will be the highest** (we also deduced that it is one of the numbers that has the max highest bit, but we don\'t need this info)\n5. Now the only remaining problem is how to we compute OR in an efficient way? \n    1. From point 1., we can simply iterate on each number and fill an array keeping track if bit `b` is set or not\n    2. We can precompute the OR bits by filling this array. Computing the value of OR is easy, we just convert the array to a number\n    3. When we multiply a number by `2^k` we simply shift its bits `k` positions higher, then we can get the result of chosing this number by adding its bits to the array.\n    4. Now there is one last trick. In 3. since we shift `num` we could by mistake consider a bit of its initial value as being set, but it was maybe the only number that had this bit. We just have to slightly modify our array to store the count of numbers having this bit. Then before shifting we decrease the count of this bit. If this count == 0 in the array it means this bit is not set.\n\n\n```\nclass Solution {\n    // normally the worst case would be 10^9 * 2^ 15, so 45 bits max but I put more just in case (so that we can handle any long)\n\tprivate static final int MAX_BITS = 63;\n\n    public long maximumOr(int[] nums, int k) {\n\t\n\t\t// precompute the array of bits\n\t\t// originalBits[i] = how many elements in nums have bit i set to one\n        int[] originalBits = new int[MAX_BITS];\n        for (int num : nums) {\n            for(int i = 0; num > 0; i++){\n                if(num%2 == 1) originalBits[i]++;\n                num /= 2;\n            }\n        }\n\n        long max = 0;\n        for (int num : nums) {\n            int[] bits = Arrays.copyOf(originalBits, MAX_BITS);\n             for(int i = 0; num > 0; i++){\n                if(num%2 == 1){ // if ith bit set\n\t\t\t\t\t// remove its old value\n                    bits[i]--;\n\t\t\t\t\t// add its new one\n                    bits[i+k]++;\n                }\n                num /= 2;\n            }\n\t\t\t// convert bits to a number\n            long result = 0;\n            for (int i = 0; i < MAX_BITS; i++) {\n                if(bits[i] > 0) result += (1L << i);\n            }\n            max = Math.max(result, max);\n        }\n\n        return max;\n\n    }\n}\n```\n\nTime complexity : `O(n)` since we simply iterate on `nums`\nSpace complexity: `O(1)` We only use one array of constant size\n\n\n# Note \nFollowing the discussion with @dinar below, from point 2. you can solve it with a different algorithm (but same complexity) by iterating on the bits and filtering out candidates that wouldn\'t produce the highest bits in the answer. \n\t<details>\n\t<summary>Reveal alternative solution</summary>\n```\nclass Solution {\n\n    private int bitAt(int num, int i){\n        return (num >> i) & 1;\n    }\n\n    public long maximumOr(int[] nums, int k) {\n        // small improvement to limit the number of bits to check\n        // we could also iterate first over all numbers to see what is the actual highest bit\n        int MAX_BITS = 30 +k;\n\n        Set<Integer> candidates = new HashSet<>();\n\n        // precompute the array of bits\n        int[] bits = new int[MAX_BITS];\n        for (int num : nums) {\n            candidates.add(num);\n            for(int i = 0; num > 0; i++){\n                if(num%2 == 1) bits[i]++;\n                num /= 2;\n            }\n        }\n\n        for (int i = MAX_BITS - 1; i >= 0; i--) {\n            Set<Integer> withBit = new HashSet<>();\n            long bitMask =  i >= k ?\n                    1L << (i-k) : // looking for a bit in position i-k\n                    i << 31; // mask impossible to match\n            for (Integer candidate : candidates) {\n                if((bitMask & candidate) > 0) withBit.add(candidate);\n                else {\n                    // we look if this bit would be set in the final result with this candidate shifted\n                    if(bits[i] - bitAt(candidate, i) > 0) withBit.add(candidate);\n                }\n            }\n\n            // if withBit.size = 0, no candidate better than the others for this bit, so we keep all the previous candidates\n            if(withBit.size() >= 1){\n                candidates = withBit;\n            }\n\n            if(candidates.size() == 1) break;  // we can stop early we found a unique winner\n        }\n\n        // take an random candidate from all the ones that provide the maximum\n        int winner = candidates.iterator().next();\n\n        for(int i = 0; winner > 0; i++){\n            if(winner%2 == 1){ // if ith bit set\n                // remove its old value\n                bits[i]--;\n                // add its new one\n                bits[i+k]++;\n            }\n            winner /= 2;\n        }\n        // convert bits to a number\n        long result = 0;\n        for (int i = 0; i < MAX_BITS; i++) {\n            if(bits[i] > 0) result += (1L << i);\n        }\n\n\n        return result;\n\n    }\n```\n\t
['Java']