3117-minimum-sum-of-values-by-dividing-array.adoc

3117. Minimum Sum of Values by Dividing Array

{leetcode}/problems/minimum-sum-of-values-by-dividing-array/[LeetCode - 3117. Minimum Sum of Values by Dividing Array ^]

You are given two arrays nums and andValues of length n and m respectively.

The value of an array is equal to the last element of that array.

You have to divide nums into m disjoint contiguous <span data-keyword="subarray-nonempty">subarrays such that for the ith subarray [l<sub>i</sub>, r<sub>i</sub>], the bitwise AND of the subarray elements is equal to andValues[i], in other words, nums[l<sub>i</sub>] & nums[l<sub>i</sub> + 1] & …​ & nums[r<sub>i</sub>] == andValues[i] for all 1 ⇐ i ⇐ m, where & represents the bitwise AND operator.

Return the minimum possible sum of the values of the _`m` subarrays `nums` is divided into_. If it is not possible to divide _`nums` into `m` subarrays satisfying these conditions, return_ -1.

Example 1:

<div class="example-block"> Input: <span class="example-io">nums = [1,4,3,3,2], andValues = [0,3,3,2]

Output: <span class="example-io">12

Explanation:

The only possible way to divide nums is:

• [1,4] as 1 & 4 == 0.

• [3] as the bitwise AND of a single element subarray is that element itself.

• [3] as the bitwise AND of a single element subarray is that element itself.

• [2] as the bitwise AND of a single element subarray is that element itself.

The sum of the values for these subarrays is 4 + 3 + 3 + 2 = 12.

Example 2:

<div class="example-block"> Input: <span class="example-io">nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

Output: <span class="example-io">17

Explanation:

There are three ways to divide nums:

• [[2,3,5],[7,7,7],[5]] with the sum of the values 5 + 7 + 5 == 17.

• [[2,3,5,7],[7,7],[5]] with the sum of the values 7 + 7 + 5 == 19.

• [[2,3,5,7,7],[7],[5]] with the sum of the values 7 + 7 + 5 == 19.

The minimum possible sum of the values is 17.

Example 3:

<div class="example-block"> Input: <span class="example-io">nums = [1,2,3,4], andValues = [2]

Output: <span class="example-io">-1

Explanation:

The bitwise AND of the entire array nums is 0. As there is no possible way to divide nums into a single subarray to have the bitwise AND of elements 2, return -1.

Constraints:

• 1 ⇐ n == nums.length ⇐ 104

• 1 ⇐ m == andValues.length ⇐ min(n, 10)

• 1 ⇐ nums[i] < 105

• 0 ⇐ andValues[j] < 105

思路分析

一刷

link:{sourcedir}/_3117_MinimumSumOfValuesByDividingArray.java[role=include]

参考资料