LC-2897 Hard LeetCode

2897. Apply Operations on Array to Maximize Sum of Squares

Array Hash Table Greedy Bit Manipulation

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 43% Topics: Array, Hash Table, Greedy, Bit Manipulation

Reading material

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

Reference solution (spoiler · python)

# Time:  O(nlogr), r = max(nums)
# Space: O(logr)

# bit manipulation, greedy, freq table
class Solution(object):
    def maxSum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        MOD = 10**9+7
        l = max(nums).bit_length()
        cnt = [0]*l
        for i in xrange(l):
            for x in nums:
                if x&(1<<i):
                    cnt[i] += 1
        return reduce(lambda x, y: (x+y)%MOD, (sum(1<<i for i in xrange(l) if cnt[i] >= j)**2 for j in xrange(1, k+1)))

Solution from kamyu104/LeetCode-Solutions · MIT