Prefix + Suffix Sum & Greedy
With bit OR operation we will collect all unique bits in array. When we multiple any number by 2 we shifts all bits to the right by 1. The most benefiting bit b
With bit OR operation we will collect all unique bits in array. When we multiple any number by 2 we shifts all bits to the right by 1. The most benefiting bit by shifting is the most significant bit in overall OR result. If we shift that bit to the right by 1 it will have even more significant power. From that observation we can understand that we need to shift number with most significant bit for k times to the right. However there could be few different numbers with most significant bits and it is not mandatory that shifting highest number will benefit more than other numbers with same most significant bits. For example, lets assume that we have total OR of array as 110011 and we have 2 numbers with most significant bits: 100001 and 100010. If our k = 2 then after shifting first number we would have 10111110 and after shifting second number we would have 10111101. In that case 10111110 > 10111101 while 100001 < 100010. Thats why we need to calculate all possible values after shifting each number and select highest one.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        int prefix = 0;\n        // We need precompute all suffixes as bit OR is irreversible operation\n        // However prefix we can compute as we go on\n        vector<int> suffix(nums.size()+1);\n        for (int i = nums.size(); i > 0; i--)\n            suffix[i-1] = suffix[i] | nums[i-1];\n\n        long long res = 0;\n        for (int i = 0; i < nums.size(); i++) {\n            long long val = nums[i];\n            // Calculate value with current number shifted by K\n            val = (val << k) | prefix | suffix[i+1];\n            res = max(res, val);\n            // Update prefix\n            prefix |= nums[i];\n        }\n        return res;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```
['C++']