#3117

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Sum of Values by Dividing Array

Solve the problem of dividing an array into subarrays to match specified bitwise AND values using dynamic programming.

array binary search dynamic programming bit manipulation segment tree

Problem Statement

You are given two arrays, nums and andValues, where nums has n elements and andValues has m elements. The goal is to divide nums into m contiguous subarrays such that for the ith subarray [li, ri], the bitwise AND of its elements equals andValues[i]. The bitwise AND operation is represented as '&'.

Return the minimum possible sum of the values of these subarrays, where the value of a subarray is the last element in it. If it's not possible to divide nums as described, return -1. The solution involves considering all valid partitions and ensuring each AND operation matches the corresponding value from andValues.

Examples

Example 1

Input: nums = [1,4,3,3,2], andValues = [0,3,3,2]

Output: 12

The only possible way to divide nums is: The sum of the values for these subarrays is 4 + 3 + 3 + 2 = 12 .

Example 2

Input: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

Output: 17

There are three ways to divide nums : The minimum possible sum of the values is 17 .

Example 3

Input: nums = [1,2,3,4], andValues = [2]

Output: -1

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

Solution Approach

State Transition Dynamic Programming

The solution can be framed using dynamic programming. Let dp[i][j] represent the optimal answer when dividing nums[0..(i-1)] into the first j subarrays. Iterate over possible splits and calculate the bitwise AND for each subarray. The dynamic programming table is filled by considering valid transitions and updating the optimal sum at each step.

Bitwise AND Calculation

Each subarray's bitwise AND must match a corresponding value from andValues. This requires efficiently computing the AND of subarrays and comparing it to the expected values. For each subarray, maintain a running AND as you extend the subarray, and check for matches with the current value in andValues.

Efficient State Updates

To ensure an efficient solution, keep track of the last bitwise AND calculated and use it to minimize redundant calculations. For each subarray split, check if the AND operation matches the corresponding value in andValues and update the DP table accordingly. This approach reduces unnecessary recomputations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach used to handle subarray splits and bitwise operations. The space complexity will also vary depending on how the DP table is implemented, but typically, it would be O(n*m), where n is the length of nums and m is the length of andValues.

What Interviewers Usually Probe

Candidate is familiar with dynamic programming for state transitions.
Candidate understands bitwise operations and how they apply to subarrays.
Candidate optimizes the solution by avoiding redundant calculations and efficiently updating states.

Common Pitfalls or Variants

Common pitfalls

Not handling edge cases where a valid division is impossible, returning -1 in such cases.
Overcomplicating the bitwise AND computation by recalculating for each subarray repeatedly.
Missing an efficient way to manage dynamic programming state transitions, leading to redundant operations.

Follow-up variants

Consider variations where the number of subarrays is increased, making it necessary to optimize the DP approach.
Differentiate the problem by changing the bitwise operation (e.g., OR instead of AND) and observe the impact on the solution.
Change the problem constraints, such as limiting the size of nums or andValues, to explore how that affects the approach.

FAQ

How do I approach solving the Minimum Sum of Values by Dividing Array problem?

Focus on dynamic programming, where you keep track of the optimal subarray splits and calculate the bitwise AND for each subarray to match andValues.

What is the most efficient way to calculate the bitwise AND for subarrays?

Use a running AND calculation as you extend the subarray, avoiding redundant recalculations by keeping track of the last AND value.

What happens if it's impossible to split nums as required in the problem?

If no valid division can be made, return -1 to indicate it's impossible to achieve the required subarrays.

How do I optimize the dynamic programming approach for this problem?

Ensure that you minimize redundant calculations in the DP table by efficiently updating the state transitions and checking each subarray's AND value against the corresponding entry in andValues.

What should I do if the number of subarrays is different from the length of andValues?

The number of subarrays must match the length of andValues. If they don't, a valid solution cannot be found, and the answer should be -1.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j, a)$, which represents the possible minimum sum of subarray values that can be obtained starting from the $i$-th element, with $j$ subarrays already divided, and the bitwise AND result of the current subarray to be divided is $a$. The answer is $dfs(0, 0, -1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, a: int) -> int:
            if n - i < m - j:
                return inf
            if j == m:
                return 0 if i == n else inf
            a &= nums[i]
            if a < andValues[j]:
                return inf
            ans = dfs(i + 1, j, a)
            if a == andValues[j]:
                ans = min(ans, dfs(i + 1, j + 1, -1) + nums[i])
            return ans

        n, m = len(nums), len(andValues)
        ans = dfs(0, 0, -1)
        return ans if ans < inf else -1

Continue Practicing

#3171 find subarray with bitwise or closest to k #3209 number of subarrays with and value of k #2945 find maximum non decreasing array length