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

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 an integer <code>k</code>.

In one operation, you can pick any index <code>i</code> of <code>nums</code> such that <code>0 &lt;= i &lt; nums.length - 1</code> and replace <code>nums[i]</code> and <code>nums[i + 1]</code> with a single occurrence of <code>nums[i] &amp; nums[i + 1]</code>, where <code>&amp;</code> represents the bitwise <code>AND</code> operator.

Return the minimum possible value of the bitwise <code>OR</code> of the remaining elements of <code>nums</code> after applying at most <code>k</code> operations.

&nbsp;
Example 1:

<pre>
Input: nums = [3,5,3,2,7], k = 2
Output: 3
Explanation: Let&#39;s do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] &amp; nums[1]) so that nums becomes equal to [1,3,2,7].
2. Replace nums[2] and nums[3] with (nums[2] &amp; nums[3]) so that nums becomes equal to [1,3,2].
The bitwise-or of the final array is 3.
It can be shown that 3 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.</pre>

Example 2:

<pre>
Input: nums = [7,3,15,14,2,8], k = 4
Output: 2
Explanation: Let&#39;s do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] &amp; nums[1]) so that nums becomes equal to [3,15,14,2,8]. 
2. Replace nums[0] and nums[1] with (nums[0] &amp; nums[1]) so that nums becomes equal to [3,14,2,8].
3. Replace nums[0] and nums[1] with (nums[0] &amp; nums[1]) so that nums becomes equal to [2,2,8].
4. Replace nums[1] and nums[2] with (nums[1] &amp; nums[2]) so that nums becomes equal to [2,0].
The bitwise-or of the final array is 2.
It can be shown that 2 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
</pre>

Example 3:

<pre>
Input: nums = [10,7,10,3,9,14,9,4], k = 1
Output: 15
Explanation: Without applying any operations, the bitwise-or of nums is 15.
It can be shown that 15 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
</pre>

&nbsp;
Constraints:

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

minOrAfterOperations

Minimize OR of Remaining Elements Using Operations

Maximum XOR After Operations 

maximum-xor-after-operations

操作后的最大异或和

Apply Operations on Array to Maximize Sum of Squares

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

对数组执行操作使平方和最大

Greedy

Bit Manipulation

Array

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

一次操作中，你可以选择 <code>nums</code>&nbsp;中满足&nbsp;<code>0 &lt;= i &lt; nums.length - 1</code>&nbsp;的一个下标 <code>i</code>&nbsp;，并将&nbsp;<code>nums[i]</code> 和&nbsp;<code>nums[i + 1]</code>&nbsp;替换为数字&nbsp;<code>nums[i] &amp; nums[i + 1]</code>&nbsp;，其中&nbsp;<code>&amp;</code>&nbsp;表示按位&nbsp;<code>AND</code>&nbsp;操作。

请你返回 至多&nbsp;<code>k</code>&nbsp;次操作以内，使 <code>nums</code>&nbsp;中所有剩余元素按位 <code>OR</code>&nbsp;结果的 最小值&nbsp;。

&nbsp;

示例 1：

<pre>
输入：nums = [3,5,3,2,7], k = 2
输出：3
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] &amp; nums[1]) ，得到 nums 为 [1,3,2,7] 。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] &amp; nums[3]) ，得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。
3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。</pre>

示例 2：

<pre>
输入：nums = [7,3,15,14,2,8], k = 4
输出：2
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] &amp; nums[1]) ，得到 nums 为 [3,15,14,2,8] 。
2. 将 nums[0] 和 nums[1] 替换为 (nums[0] &amp; nums[1]) ，得到 nums 为 [3,14,2,8] 。
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] &amp; nums[1]) ，得到 nums 为 [2,2,8] 。
4. 将 nums[1] 和 nums[2] 替换为 (nums[1] &amp; nums[2]) ，得到 nums 为 [2,0] 。
最终数组的按位或值为 2 。
2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
</pre>

示例 3：

<pre>
输入：nums = [10,7,10,3,9,14,9,4], k = 1
输出：15
解释：不执行任何操作，nums 的按位或值为 15 。
15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
</pre>

&nbsp;

提示：

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