[Python3] Two Counters, Constant Space, Lots of Bit Hacks
Disclaimer\nI wasn\'t able to crack this question during the contest; I figured out the trick but wasn\'t able to implement it nor rigorously prove why it works
# Disclaimer\nI wasn\'t able to crack this question during the contest; I figured out the trick but wasn\'t able to implement it nor rigorously prove why it works. Other solutions do a good job with the proof so I\'ll just explain my intuition down below.\n\n# Trick\nWe want to find the maximal array OR (`nums[0] | nums[1] | ... | nums[n - 1]`), where we can multiply by 2 any values (possibly different ones) in the array, for a total of k multiplications. Immediately, because we\'re multiplying by 2 and trying to maximize a bitwise operation, we should realize that multiplying by 2 is equivalent to a single left shift.\n\nIt also turns out that it\'s best to select only one value to be shifted k times. This makes sense because, by shifting say the largest value k times, we can achieve a really big single value to be used in our array OR operation. However, choosing the maximum value in the array doesn\'t necessarily work (see the given example [12, 9]).\n\n# Algorithm\nA correct algorthm will do the following:\n1. Figure out the candidates to be shifted (one pass)\n2. For each number in the array (second pass)\n  a. If the number is a candidate, do the below\n  b. Compute the OR of the array, discluding the candidate; `curr_removed`\n  c. Compute the candidate, shifted left `k` times; `shifted`\n  d. Set the result to be the larger between the result and `shifted | curr_removed`\n\nYou\'ll notice that this approach would run in quadratic time since we\'re recomputing the array OR not including the candidate each time. Because the same bit can be included multiple times, we need to be smart about this, which is explained in the implementation.\n\n# Implementation + Bithacks\nSince we need to compute the array OR quickly and need only to simulate removing a single candidate, it makes sense to precompute this in a single pass for constant lookup later. However, it\'s not entirely clear exactly how to remove a candidate from an array OR from a first glance. If we re-think the array OR, we\'ll notice that it\'s equal to an OR of two components:\n\n`array OR = bits_appearing_exactly_once | bits_appearing_two_or_more_times`\n\nSo, in our first pass that computes the candidates to be shifted, we can also compute the two bitsets as well (`once` and `two_or_more`).\n\nNote that calculating the above bitsets can be done using only bit operations in an iterative way, for each number `curr = nums[i]`. Note that the order of how we\'re calculating `two_or_more` and `once` matters.\n\n`two_or_more = two_or_more | (once & curr)`.\n- Doing `two_or_more | ...` indicates we\'re keeping the current bits set two or more times, as desired.\n- `once & curr` keeps bits that have appeared exactly once and are present in `curr`, which is equal to the bits that appear exactly twice within `curr`.\n\n`once = ~two_or_more & (once | curr)`\n- `~two_or_more & ...` means that we\'re using our updated `two_or_more` and making it so that any bits that are set in it **are cleared** in our computation of `once`\n- `once | curr` simply tracks bits that had appeared once and possibly new bits present in `curr`.\n\nWith `once` and `two_or_more` computed, simulating the removal of a candidate from the array OR is more straightforward:\n`array OR with candidate shifted = two_or_more | (once & ~curr) | (curr << k)`\n- The bits in `two_or_more` are kept because removing of the bits in `curr` wouldn\'t have affected the presence of these bits when calculating the rest of the array OR\n- `once & ~curr` keeps the bits appearing once while also simulating the removal of the bits set in `curr`\n- `curr << k` left shifts `curr` the required number of times.\n\n# Code\n```\nclass Solution:\n    def maximumOr(self, nums: List[int], k: int) -> int:\n        # maximumOr calculation: the best result should be the maximal value of:\n        # OR(nums[i], i != j) | nums[j] << k, for each j. Not too sure why.\n        # Compute bit counts efficiently in first pass      \n        once, two_or_more = 0, 0 # track bits appearing exactly one time, bits appearing two+ times\n        highest_bit = 0 # only need to promote the numbers with the highest bit set\n        for curr in nums:\n            highest_bit = max(highest_bit, curr.bit_length()) # track highest bit set using built-in bit_length\n            two_or_more_next = two_or_more | ( # keep current two or more\n                once & curr\n            )\n            two_or_more = two_or_more_next # things that have appeared 2+ times updated            \n            once_next = ~two_or_more & ( # zero out things appearing two/more times using updated two/more\n                once | # things that have appeared once are kept\n                curr   # curr in binary = things that have appeared once\n            )\n\n            once = once_next\n\n        # maximumOr calculation\n        res = 0\n        for curr in nums:\n            if curr.bit_length() != highest_bit: # not a candidate for promotion\n                continue\n            shifted = curr << k\n            curr_removed = once & ~curr # clear curr from once\n            cand = two_or_more | shifted | curr_removed\n            res = max(res, cand)\n\n        return res\n```
['Python3']