<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>You can do the following operation on the array <strong>any</strong> number of times:</p>

<ul>
	<li>Choose any two distinct indices <code>i</code> and <code>j</code> and <strong>simultaneously</strong> update the values of <code>nums[i]</code> to <code>(nums[i] AND nums[j])</code> and <code>nums[j]</code> to <code>(nums[i] OR nums[j])</code>. Here, <code>OR</code> denotes the bitwise <code>OR</code> operation, and <code>AND</code> denotes the bitwise <code>AND</code> operation.</li>
</ul>

<p>You have to choose <code>k</code> elements from the final array and calculate the sum of their <strong>squares</strong>.</p>

<p>Return <em>the <strong>maximum</strong> sum of squares you can achieve</em>.</p>

<p>Since the answer can be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,6,5,8], k = 2
<strong>Output:</strong> 261
<strong>Explanation:</strong> We can do the following operations on the array:
- Choose i = 0 and j = 3, then change nums[0] to (2 AND 8) = 0 and nums[3] to (2 OR 8) = 10. The resulting array is nums = [0,6,5,10].
- Choose i = 2 and j = 3, then change nums[2] to (5 AND 10) = 0 and nums[3] to (5 OR 10) = 15. The resulting array is nums = [0,6,0,15].
We can choose the elements 15 and 6 from the final array. The sum of squares is 15<sup>2</sup> + 6<sup>2</sup> = 261.
It can be shown that this is the maximum value we can get.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,5,4,7], k = 3
<strong>Output:</strong> 90
<strong>Explanation:</strong> We do not need to apply any operations.
We can choose the elements 7, 5, and 4 with a sum of squares: 7<sup>2</sup> + 5<sup>2</sup> + 4<sup>2</sup> = 90.
It can be shown that this is the maximum value we can get.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        #basically, we want to get k elements very large
        '''
        1, 8
        k = 2
        0, 9 -> 81
        k = 1:
        0, 9 -> 81
        Either we'll include a number in the final answer or we won't. If we don't,
        Merging 1 with one that's higher will always increase the overall sum
        If you move one bit over to it, you'll be multiplying that bit by a larger number
        If you sort nums and only look at the first k elements, then apply the operation to the 
        rest of the elements

        So:
        -sort the array
        -starting from the left, change all the 0s to 1s that you can
        -subtract those from the total number of 1s in each position
        
        Only the first k numbers matter, and we should add as many bits as possible to the highest
        number since each bit counts extra for it. So,
        make 32 min heaps with each 
        '''
        bits = [0 for i in range(32)]
        for num in nums:
            for i in range(0, 32):
                bits[31-i] += num % 2
                num //= 2
                
        ans = 0
        for i in range(0, k):
            curNum = 0
            for j in range(0, 32):
                curNum *= 2
                if bits[j] > 0:
                    curNum += 1
                    bits[j] -= 1
            ans += curNum ** 2

        return ans % (10 ** 9 + 7)
            
             

2358