Problem statement

https://binarysearch.com/problems/Bit-Sum/

Solution

For each digit place, evaluate how many zeroes we have in this place. Then do the second pass, where we start with the smallest places first.

Complexity

It is O(n * M), where M = 32 here (or can be taken as maximum number of bits for number in array).

Code

class Solution:
    def solve(self, nums, k):
        cnt, MOD = [0] * 32, 10**9 + 7
        for num in nums:
            for j in range(32):
                cnt[j] += 1 - (num >> j & 1)

        ans = sum(nums)
        for i in range(32):
            n = min(cnt[i], k)
            ans += n * (1 << i)
            k -= n

        return ans % MOD