apply-operations-on-array-to-maximize-sum-of-squares

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

<ul>
	<li>Choose any two distinct indices <code>i</code> and <code>j</code> and simultaneously 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>

You have to choose <code>k</code> 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 <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

maxSum

Apply Operations on Array to Maximize Sum of Squares

Minimize OR of Remaining Elements Using Operations

minimize-or-of-remaining-elements-using-operations

给定操作次数内使剩余元素的或值最小

Greedy

Bit Manipulation

Array

Hash Table

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个 正&nbsp;整数&nbsp;<code>k</code>&nbsp;。

你可以对数组执行以下操作 任意次&nbsp;：

<ul>
	<li>选择两个互不相同的下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，同时&nbsp;将&nbsp;<code>nums[i]</code>&nbsp;更新为&nbsp;<code>(nums[i] AND nums[j])</code> 且将&nbsp;<code>nums[j]</code>&nbsp;更新为&nbsp;<code>(nums[i] OR nums[j])</code>&nbsp;，<code>OR</code>&nbsp;表示按位 或&nbsp;运算，<code>AND</code>&nbsp;表示按位 与&nbsp;运算。</li>
</ul>

你需要从最终的数组里选择&nbsp;<code>k</code>&nbsp;个元素，并计算它们的 平方&nbsp;之和。

请你返回你可以得到的 最大&nbsp;平方和。

由于答案可能会很大，将答案对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;后返回。

&nbsp;

示例 1：

<pre>
输入：nums = [2,6,5,8], k = 2
输出：261
解释：我们可以对数组执行以下操作：
- 选择 i = 0 和 j = 3 ，同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ，结果数组为 nums = [0,6,5,10] 。
- 选择 i = 2 和 j = 3 ，同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ，结果数组为 nums = [0,6,0,15] 。
从最终数组里选择元素 15 和 6 ，平方和为 152 + 62 = 261 。
261 是可以得到的最大结果。
</pre>

示例 2：

<pre>
输入：nums = [4,5,4,7], k = 3
输出：90
解释：不需要执行任何操作。
选择元素 7 ，5 和 4 ，平方和为 72 + 52 + 42 = 90 。
90 是可以得到的最大结果。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>