CPP Optimized Solution with 100% better Runtime and Memory
Intuition\nThe best approach would be to shift any one of the numbers by k bits. Our bits can be of three types.\n\n- Appearing in no number\n- Appearing in jus
# Intuition\nThe best approach would be to shift any one of the numbers by k bits. Our bits can be of three types.\n\n- Appearing in no number\n- Appearing in just one number\n- Appearing in > 1 numbers\n\nNote that the last type of bits will always be set regardless of our operation.\n\n# Approach\nUse two integers, ```single``` and ```multi``` to track the two types of bits. Any bit unset in ```single``` doesn\'t appear anywhere in our numbers. A set bit in ```single``` denotes a bit appearing only once in the whole list of our numbers. A bit set in ```multi``` means a bit set in more than one number.\n\nThe code which handles this is \n```cpp []\nint single = 0, multi = 0;\n\nfor (int num : nums) {\n    for (int j = 1; num; j <<= 1, num >>= 1) {\n        if (num & 1) {\n            multi |= single & j;\n            single |= j; \n        }\n    }\n}\n```\n\nNow that we have ```single``` and ```multi```, we can move ahead. Note that ```single``` also represents the bitwise-or of the whole list of numbers.\n\nFor each number, we want the effect of shifting it by k bits on the total bitwise-or of all the numbers.\n\nThis is computed by \n\n```cpp []\nsingle & ~num | multi | (long long)num << k\n```\n\nAny bits which were set in single because of them being present in ```num```, we need to unset those, as we are shifting the bits of ```num```. ```single & ~num ``` accomplishes this. Then all the bits in `multi` will anyway be set. Finally, since `num` was shifted `k`, we or with that too.\n\n# Complexity\n- Time complexity:\n`O(n log m)`, where `m` is the greatest element in our list. Other other bit analysis solutions claim `O(n)`, which is wrong as we always need to analyze bits, and that adds `O(log m)`. If we were doing it via prefix and suffix arrays, then yes, the complexity is `O(n)`. But those use up `O(n)` space.  \n\n- Space complexity:\n`O(1)`. Trivial to see. All other solutions with a claimed `O(1)` space use a vector to track how many times each bit is set, but that is wasteful, because as far we are concerned, it doesn\'t matter if a bit is set twice or a thousand times, it behaves the same. As said above, there are only 3 types of bits, so using two integers suffices. It also helps with direct calculation of results.\n\n![image.png](https://assets.leetcode.com/users/images/b82c1fa4-5fe0-4885-9c9d-62c3e82beefc_1729835314.4702005.png)\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        int single = 0, multi = 0;\n\n        for (int num : nums) {\n            for (int j = 1; num; j <<= 1, num >>= 1) {\n                if (num & 1) {\n                    multi |= single & j;\n                    single |= j; \n                }\n            }\n        }\n\n        long long res = 0;\n\n        for (int num : nums) res = max(res, single & ~num | multi | (long long)num << k);\n\n        return res;\n    }\n};\n```
['C++']