Algorithms
Hard
2897
3153
Apply Operations on Array to Maximize Sum of Squares
apply-operations-on-array-to-maximize-sum-of-squares
"""
You are given a 0-indexed integer array nums and a positive integer k.

You can do the following operation on the array any number of times:

 * Choose any two distinct indices i and j and simultaneously update the values of nums[i] to (nums[i] AND nums[j]) and nums[j] to (nums[i] OR nums[j]). Here, OR denotes the bitwise OR operation, and AND denotes the bitwise AND operation.

You have to choose k elements from the final array and calculate the sum of their squares.

Return the maximum sum of squares you can achieve.

Since the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: nums = [2,6,5,8], k = 2
Output: 261
Explanation: 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 152 + 62 = 261.
It can be shown that this is the maximum value we can get.

Example 2:

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


Constraints:

 * 1 <= k <= nums.length <= 105
 * 1 <= nums[i] <= 109
"""
class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        
You are given a 0-indexed integer array nums and a positive integer k.

You can do the following operation on the array any number of times:

 * Choose any two distinct indices i and j and simultaneously update the values of nums[i] to (nums[i] AND nums[j]) and nums[j] to (nums[i] OR nums[j]). Here, OR denotes the bitwise OR operation, and AND denotes the bitwise AND operation.

You have to choose k elements from the final array and calculate the sum of their squares.

Return the maximum sum of squares you can achieve.

Since the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: nums = [2,6,5,8], k = 2
Output: 261
Explanation: 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 152 + 62 = 261.
It can be shown that this is the maximum value we can get.

Example 2:

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


Constraints:

 * 1 <= k <= nums.length <= 105
 * 1 <= nums[i] <= 109


Please complete the code below to solve above prblem:
```python
class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [2,6,5,8], "k": 2 }
assert my_solution.maxSum(**test_input) == 261

test_input = { "nums": [4,5,4,7], "k": 3 }
assert my_solution.maxSum(**test_input) == 90

test_input = { "nums": [32,85,61], "k": 1 }
assert my_solution.maxSum(**test_input) == 15625

test_input = { "nums": [123], "k": 1 }
assert my_solution.maxSum(**test_input) == 15129

test_input = { "nums": [96,66,60,58,32,17,63,21,30,44,15,8,98,93], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [30,8,63,69,52,94,41,28,94,86,28,13,68,38,53,11,21,33], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [2,38,15,2,73,100,47,14,25,58,40,64,23,9,53,38,91,75,9,2], "k": 3 }
assert my_solution.maxSum(**test_input) == 48387

test_input = { "nums": [25,52,75,65], "k": 4 }
assert my_solution.maxSum(**test_input) == 24051

test_input = { "nums": [96,36,72,61,13,25,5,33,9,51,9,78,40], "k": 13 }
assert my_solution.maxSum(**test_input) == 53776

test_input = { "nums": [38,21,15,84,65,35,57,82,94,26,27,89,73,22,25,6,97,17], "k": 4 }
assert my_solution.maxSum(**test_input) == 64516

test_input = { "nums": [18,72,52,56,7,21,55,68,98,31,35,49,100,49,64,20], "k": 4 }
assert my_solution.maxSum(**test_input) == 62548

test_input = { "nums": [2,73,75], "k": 3 }
assert my_solution.maxSum(**test_input) == 11250

test_input = { "nums": [73,37,41,84], "k": 2 }
assert my_solution.maxSum(**test_input) == 27506

test_input = { "nums": [62,83,11,3,53], "k": 3 }
assert my_solution.maxSum(**test_input) == 20459

test_input = { "nums": [53,59,71,38,5,15,98,86,9,8,35,54,65,77,3,68,11,5,41,18], "k": 9 }
assert my_solution.maxSum(**test_input) == 95273

test_input = { "nums": [53,67,91,79,21,27,63,34,60,94,51], "k": 4 }
assert my_solution.maxSum(**test_input) == 64516

test_input = { "nums": [41,15,6,31,40,97,11,45,81,91,91,62], "k": 3 }
assert my_solution.maxSum(**test_input) == 48387

test_input = { "nums": [10,9], "k": 2 }
assert my_solution.maxSum(**test_input) == 185

test_input = { "nums": [9,6,8,32,92,12,47,45,62,96,5,66,82,90,34,39,49,86,16], "k": 13 }
assert my_solution.maxSum(**test_input) == 102770

test_input = { "nums": [1,19,29,30,68,13,80,16,71,32,8,76,41,24,16,2,30], "k": 14 }
assert my_solution.maxSum(**test_input) == 53470

test_input = { "nums": [22,64,30,71,28,69,86,12,26,39,69,92], "k": 2 }
assert my_solution.maxSum(**test_input) == 25154

test_input = { "nums": [91,26,29,38,97,40,1,18,15,3,43,37,9,55,4,46], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [27,73], "k": 1 }
assert my_solution.maxSum(**test_input) == 8281

test_input = { "nums": [12,33,29,75,94,48,25,21], "k": 8 }
assert my_solution.maxSum(**test_input) == 34565

test_input = { "nums": [39,91,84,10,65,28,94,28,62,77,78,50,93,65,21,16,5,35,81], "k": 14 }
assert my_solution.maxSum(**test_input) == 110106

test_input = { "nums": [14,45,76,33,35,53,67,19,6,31,33], "k": 10 }
assert my_solution.maxSum(**test_input) == 40008

test_input = { "nums": [59,88,2,47,75], "k": 2 }
assert my_solution.maxSum(**test_input) == 31258

test_input = { "nums": [96,77,77,33,5,86,90,21,84,73,86,45,88,35,93,14,63,25], "k": 17 }
assert my_solution.maxSum(**test_input) == 121571

test_input = { "nums": [35,5,21,65,34,90,60,8,34,35,28,78,77], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [14,10,19], "k": 2 }
assert my_solution.maxSum(**test_input) == 1061

test_input = { "nums": [100,4,88,29,13,78,89,11,62,63,66,46,99,87,41,29,36,71,57], "k": 18 }
assert my_solution.maxSum(**test_input) == 129739

test_input = { "nums": [86,52,100,68,30,40,49,28,61,30,3,80], "k": 11 }
assert my_solution.maxSum(**test_input) == 69063

test_input = { "nums": [29,30,61,12,98,95], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [23,13,35,41,29,57,84,67,70,96,55,85,15,72,23,52,1,11,62,1], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [34,60,85,22,83], "k": 2 }
assert my_solution.maxSum(**test_input) == 30290

test_input = { "nums": [65,26,44,70,79,65,46,18], "k": 8 }
assert my_solution.maxSum(**test_input) == 44587

test_input = { "nums": [99,50,13,62,12,60,6,29], "k": 6 }
assert my_solution.maxSum(**test_input) == 28071

test_input = { "nums": [73,66,75,44], "k": 3 }
assert my_solution.maxSum(**test_input) == 23130

test_input = { "nums": [43,85,7,66,16,96], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [45,5,3,84,81,54,21,37,99,60], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [97,6,44,57,63,5], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [65,43,82,46,34,42,65,67,8,67,3,83,87,71,98,31,15,22], "k": 5 }
assert my_solution.maxSum(**test_input) == 80645

test_input = { "nums": [79,33,75,32,64,68,30,46,60,50,6,54,18,34,43,11,84,78,54,4], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [17,9,3,23,33,99,94,15,93,17,39,55,13,26,22,44,13], "k": 3 }
assert my_solution.maxSum(**test_input) == 48387

test_input = { "nums": [83,29,2,67,79,88,71,98,70], "k": 4 }
assert my_solution.maxSum(**test_input) == 39220

test_input = { "nums": [60,81,60,88,37,38,10,42,84,70], "k": 10 }
assert my_solution.maxSum(**test_input) == 67626

test_input = { "nums": [33,51,100,33,46], "k": 3 }
assert my_solution.maxSum(**test_input) == 18739

test_input = { "nums": [29,4,67,44,74,62,41,86,91,11,26,58,59,48,46,41,26,68,4,81], "k": 4 }
assert my_solution.maxSum(**test_input) == 64516

test_input = { "nums": [86,54,20,57,87,63,2,24,73,87,7,16,50,1,58], "k": 7 }
assert my_solution.maxSum(**test_input) == 69543

test_input = { "nums": [91,2,16,77,2], "k": 1 }
assert my_solution.maxSum(**test_input) == 9025

test_input = { "nums": [19,94], "k": 2 }
assert my_solution.maxSum(**test_input) == 9349

test_input = { "nums": [14,67,79,58], "k": 2 }
assert my_solution.maxSum(**test_input) == 22370

test_input = { "nums": [44,17,10,19,3,97,45,65,98,7,73,30,76,5,52,33,62], "k": 4 }
assert my_solution.maxSum(**test_input) == 64516

test_input = { "nums": [8,80,93], "k": 1 }
assert my_solution.maxSum(**test_input) == 8649

test_input = { "nums": [51,79,26,30,41,74,6,11,10,66,61,25,41,32,83,52,71,70], "k": 18 }
assert my_solution.maxSum(**test_input) == 98085

test_input = { "nums": [15,58,38,69,71,43], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [13,57,34,69,80,98,63,22,29,38,70,94,79,95,13,76,39,22], "k": 5 }
assert my_solution.maxSum(**test_input) == 80645

test_input = { "nums": [98,88,17,85,57,97,42,15,25,71,31,72,76,89,28,47,73,85], "k": 9 }
assert my_solution.maxSum(**test_input) == 114889

test_input = { "nums": [95,28,26,65,87,4,14,25,47,97,67,48,29,14,96,76,77,25], "k": 9 }
assert my_solution.maxSum(**test_input) == 100409

test_input = { "nums": [37,16,76,9,88,44,71,61,95,32,63,10,29,33], "k": 11 }
assert my_solution.maxSum(**test_input) == 72360

test_input = { "nums": [54,96,73,18,15,35,79,96,2,12,50,75,7,93,66,35,40,16], "k": 18 }
assert my_solution.maxSum(**test_input) == 104436

test_input = { "nums": [66,84,85,7,45,34,61,91,83,13,87,89,51,52,65], "k": 6 }
assert my_solution.maxSum(**test_input) == 88214

test_input = { "nums": [76,22,86,88,58,10,61,21,42], "k": 2 }
assert my_solution.maxSum(**test_input) == 32258

test_input = { "nums": [16,52,8,99,68,73], "k": 2 }
assert my_solution.maxSum(**test_input) == 31754

test_input = { "nums": [46,91,73,38,36,79,24,78,24,42], "k": 8 }
assert my_solution.maxSum(**test_input) == 60911

test_input = { "nums": [5,100,85,52,5,28,79,30,9,67,87,50,17,29,99,57], "k": 14 }
assert my_solution.maxSum(**test_input) == 91019

test_input = { "nums": [52,57,77,95,79,28,9,94,70,8,89,75,27,53,41,88,68,8,10,59], "k": 5 }
assert my_solution.maxSum(**test_input) == 80645

test_input = { "nums": [66,64,52,90,73,84,2], "k": 6 }
assert my_solution.maxSum(**test_input) == 39881

test_input = { "nums": [97,100], "k": 1 }
assert my_solution.maxSum(**test_input) == 10201

test_input = { "nums": [27,85,57,44,16,55,77,77,24,62,72], "k": 10 }
assert my_solution.maxSum(**test_input) == 66334

test_input = { "nums": [15,6,18,22,72,63,38,72,4,84,9,19,70,76,72,98,35,51,11,9], "k": 20 }
assert my_solution.maxSum(**test_input) == 96344

test_input = { "nums": [10,67,54,100,6,93,91,4,59], "k": 3 }
assert my_solution.maxSum(**test_input) == 48387

test_input = { "nums": [90,48,91,62,39,94,75,8,21,72,9,55,16,30,27,73,81,39,97], "k": 8 }
assert my_solution.maxSum(**test_input) == 114080

test_input = { "nums": [43,58,51,40,39,92,36,57], "k": 4 }
assert my_solution.maxSum(**test_input) == 27548

test_input = { "nums": [85,51,49,13,7,66,21,59,100,14,5,66], "k": 8 }
assert my_solution.maxSum(**test_input) == 63152

test_input = { "nums": [54,52,36,17,34,100,81,82,16,46,26,73,77,55,43,53], "k": 14 }
assert my_solution.maxSum(**test_input) == 91703

test_input = { "nums": [97,1,30,41,82,77,99,56,21,68,14,39,15,26,72], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [17,10,28,78,68,68,29,44], "k": 5 }
assert my_solution.maxSum(**test_input) == 33906

test_input = { "nums": [59,30,26,58,87,1,6,98,29,50,57,64,64], "k": 10 }
assert my_solution.maxSum(**test_input) == 69321

test_input = { "nums": [77,23,43,94,74,41,26,39,83,57,85,49,83,34,63,37,42,55,20,18], "k": 3 }
assert my_solution.maxSum(**test_input) == 48387

test_input = { "nums": [54,19,69,95,26,59,68,90,77,62,67,54,42,25,50,23,30,53,29,78], "k": 12 }
assert my_solution.maxSum(**test_input) == 117170

test_input = { "nums": [54,17,16,30,35,63,34,38,26,41,33], "k": 9 }
assert my_solution.maxSum(**test_input) == 22133

test_input = { "nums": [17,24,8,57,68,54,64,53], "k": 6 }
assert my_solution.maxSum(**test_input) == 35987

test_input = { "nums": [11,90,27,72,22,24,54,64,68,94,1,20,45,5,63], "k": 10 }
assert my_solution.maxSum(**test_input) == 69082

test_input = { "nums": [92,84,89,72,80,1,8], "k": 3 }
assert my_solution.maxSum(**test_input) == 25042

test_input = { "nums": [29,14,37,61,7,10,53,95,47,81,1,59,18,25,3,53,43,64,33], "k": 5 }
assert my_solution.maxSum(**test_input) == 56325

test_input = { "nums": [44,94,83,38,63,16,45,90,74,20], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [13,65], "k": 2 }
assert my_solution.maxSum(**test_input) == 5930

test_input = { "nums": [16,9,2,66], "k": 2 }
assert my_solution.maxSum(**test_input) == 8285

test_input = { "nums": [30,68,85,13,49,96,59,61,39], "k": 7 }
assert my_solution.maxSum(**test_input) == 54942

test_input = { "nums": [29,47,38,4], "k": 2 }
assert my_solution.maxSum(**test_input) == 6178

test_input = { "nums": [49,30], "k": 2 }
assert my_solution.maxSum(**test_input) == 4225

test_input = { "nums": [64,71,33,46,77,45,33,55,84,30,1,40,2,92,54,88], "k": 8 }
assert my_solution.maxSum(**test_input) == 98815

test_input = { "nums": [55,72,75], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [3,34,63,27,49,28,86], "k": 3 }
assert my_solution.maxSum(**test_input) == 24067

test_input = { "nums": [99,29,94,21,54,43,20,79,27,40,90,76,55,27,40,46,76,70,34], "k": 13 }
assert my_solution.maxSum(**test_input) == 118264

test_input = { "nums": [64,11,2,12,11,82,10,42,63,98,99,13], "k": 1 }
assert my_solution.maxSum(**test_input) == 16129

test_input = { "nums": [23,25,45,88,88,93,91,25,34,83,9,85,18], "k": 8 }
assert my_solution.maxSum(**test_input) == 67760

test_input = { "nums": [84,95,7,53,19,46,41,48,48,38], "k": 7 }
assert my_solution.maxSum(**test_input) == 44981

test_input = { "nums": [92,88,27,34], "k": 4 }
assert my_solution.maxSum(**test_input) == 24805