Why (num << k) explanation | Simple & Easy step by step thinking process | Easy | Prefix Sum | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nWe start by checking the binary representation of the numbers.\n\nLet\'s take an exampl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe start by checking the binary representation of the numbers.\n\nLet\'s take an example: \n\n`nums = [1,2], k = 2`\n\nWe write the numbers in their binary represenations.\n\n1 -> `1` | 2 -> `10`\n\n**Observation 1:** The maximum number that can be made is by multiplying the number with maximum number of bits in it\'s binary representation.\n\nIn this example, we have k = 2, We have 3 cases:\n- We use both operations for `idx: 0` then we will convert 1 (`1`) -> 4 (`100`) and our result will be `4 | 2 = 6`\n- We use one operation for `idx: 0` and the second one for `idx: 1` then we will convert 1 (`1`) -> 2 (`10`) and 2 (`10`) -> 4 (`100`) and our result will be `2 | 4 = 6`\n- We use both for `idx: 1` then we will convert 2 (`10`) -> 8 (`1000`) and our result will be `1 | 8 = 9`\n\nIt can be observed that performing the operations on the number which has highest number of bits can give us the maximum result, which is `9` for this example.\n\nHere\'s the second case what if we have multiple numbers sharing the maximum number of bits.\n\nLet\'s take an example again:\n\n`nums = [12,9], k = 2`\n\nHere we have 12 -> `1100` and 9 -> `1001`\n\nBoth of them have maximum number of bits which is 4. Here we have k = 2.\n\n - Supose we apply first operation on `idx: 0` then it will become 12 (`1100`) -> 24 (`11000`) and the other number would be 9 (`1001`)\n - Now we only applied one operation and we still have one operation left (initially `k=2`)\n - Now our array is `[24, 9]`\n - Now we can see that 24 (`11000`) has maximum number of bits and according to the `Observation 1`, applying all operations on it will give us the maximum result for the array -> `[24, 9]`\n - After apply the rest of the operations on `24` our array becomes `[48, 9]` our final result becomes `48 | 9 = 57`\n\nNow we apply the same thing we `idx: 1`\n- Apply one operation then it will become 9 (`1001`) -> 18 (`10010`).\n- Our new array is `[12, 18]`\n- Now we can see that 18 (`10010`) has maximum number of bits and according to the `Observation 1`, applying all operations on it will give us the maximum result for the array -> `[12, 18]`\n- After apply the rest of the operations on `18` our array becomes `[12, 36]` our final result becomes `12 | 36 = 44`\n\nNow our final answer for the array `[12, 9]` and `k=2` will be the maximum of `57` and `44` which is `57`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Base Case: If the size of the input is `1` we can just return `nums[0]*k`\n- Now we loop over the input array and for each index we use all the operations on the current index that is `nums[idx]*k`\nTo calculate the answer for this index, we also need the OR of the rest of the elements. For this we use prefix and suffix array.\n- We build the prefix and suffix array.\n```\n        vector<long long> pref(n+1), suff(n+1);\n        \n\n        for (int i = 0; i < n; i++) {\n            pref[i + 1] = pref[i] | nums[i];\n        }\n\n        for (int i = n - 1; i >= 0; i--) {\n            suff[i] = suff[i + 1] | nums[i];\n        }\n```\n- To calucalte the answer for the current index we have three thing to consider `pref[i]`, `nums[idx]*k` and `suff[i+1]`.\n- The result for current index will be `pref[i] | nums[idx] * k | suff[i+1]`\n- Our final answer will be the maximum of the results we get from each index.\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n- Here we are computing prefix OR on the fly.\n```\nclass Solution {\npublic:\n    typedef long long ll;\n\n    long long maximumOr(vector<int> &nums, int k) {\n        int n = nums.size();\n        if(n == 1)\n            return nums[0]*1LL << k;\n\n        vector<ll> suff(n+1);\n        \n        for (int i = n - 1; i >= 0; i--) {\n            suff[i] = suff[i + 1] | nums[i];\n        }\n\n        int preOR = 0;\n\n        ll ans = 0;\n        for(int i =0; i < n; i++) {\n            ll curr = nums[i]*1LL << k;\n            ll tmp = preOR | curr | suff[i+1];\n            preOR |= nums[i];\n            ans = max(ans, tmp);\n        }\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'Prefix Sum', 'C++']