LC-3022 Hard LeetCode

3022. Minimize OR of Remaining Elements Using Operations

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 29% Topics: Array, Greedy, Bit Manipulation

Reading material

Arrays & Hashing 12 min Greedy 11 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(nlogr)
# Space: O(1)

# bitmasks, greedy
class Solution(object):
    def minOrAfterOperations(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = 0
        l = max(nums).bit_length()
        mask = (1<<l)-1
        for i in reversed(xrange(l)):
            result <<= 1
            curr, cnt = mask, 0
            for x in nums:
                curr &= x>>i
                if curr&~result:
                    cnt += 1
                else:
                    curr = mask
            if cnt > k:
                result += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT