100087.对数组执行操作使平方和最大
题目描述:
给你一个下标从 0 开始的整数数组 nums
和一个 正 整数 k
。
你可以对数组执行以下操作 任意次 :
- 选择两个互不相同的下标
i
和j
,同时 将nums[i]
更新为(nums[i] AND nums[j])
且将nums[j]
更新为(nums[i] OR nums[j])
,OR
表示按位 或 运算,AND
表示按位 与 运算。
你需要从最终的数组里选择 k
个元素,并计算它们的 平方 之和。
请你返回你可以得到的 最大 平方和。
由于答案可能会很大,将答案对 $10^9 + 7$ 取余 后返回。
数据范围:
$1\le k \le nums.len \le 10^5; 1\le nums[i] \le 10^9$
题解:
x + y = x & y + x | y
。因为两个数同一位同时为 $0$ 或 $1$ ,x & y
,x | y
同一位结果是不会变的,而同一位不同时,相当于交换了 $0,1$ 。即 $x$ 减少了 $d$ , $y$ 增加了 $d$ 。
假设原值: $x^2 + y ^2$ , $x < y$
交换后: $(x - d)^2 + (y + d)^2 = x^2 + y^2 + 2\times(y - x)\times d + 2d^2 \gt x^2 + y^2$ 。
通过交换之后数值变大了,因此应该通过交换,尽量得到更大的数。
可以考虑统计所有数的每一位上 $1$ 的个数。然后假设这些 $1$ 通过交换,全移动到了一个数上,这样就可以得到最大的数。每次这样进行,直到取出了 $k$ 个数,或者构造出的数为 $0$ 。
代码:
1 | class Solution |