Skip to content

Practice Minimum Sum of Values by Dividing Array

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3117
LeetCode Problem

Minimum Sum of Values by Dividing Array

Problem Statement

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 subarrays such that for the ith subarray [li, ri], the bitwise AND of the subarray elements is equal to andValues[i], in other words, nums[li] & nums[li + 1] & ... & nums[ri] == 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.

Source: Minimum Sum of Values by Dividing Array on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [1,4,3,3,2], andValues = [0,3,3,2]
Output
12
Explanation

The partition [1,4] | [3] | [3] | [2] has segment AND values 0, 3, 3 and 2, exactly matching andValues. The charged values are the last elements, so the cost is 4 + 3 + 3 + 2 = 12, not the sum of all input values. Four non-empty segments must cover five numbers, leaving room for only one segment of length two. The first segment needs at least [1,4] to make its AND zero, which fixes the entire partition and proves 12 is minimal.

# Example 2

Input
nums = [2,3,5,7,7,7,5], andValues = [0,7,5]
Output
17
Explanation

Use [2,3,5] | [7,7,7] | [5]. Their AND values are 0, 7 and 5, while their last elements sum to 5 + 7 + 5 = 17. This is minimal: the first segment cannot reach AND 0 before the initial 5, and every later feasible first endpoint has value 7. The middle segment must consist of 7s to retain all three bits of 7. The final segment must end at the array's last 5. Thus the three endpoint costs are at least 5, 7 and 5. Minimize endpoint values, not segment lengths.

# Example 3

Input
nums = [1,2,3,4], andValues = [2]
Output
-1
Explanation

There is only one required segment, so it must contain the entire array [1,2,3,4]. Already 1 & 2 = 0, and ANDing additional numbers cannot restore a cleared bit, so the full AND is 0 rather than the required 2. The result is -1. Finding a smaller subarray such as [2] with AND 2 would not solve this instance: the partition must cover every input element exactly once, in order, using exactly one non-empty segment.

Constraints

1 <= n == nums.length <= 10^4
1 <= m == andValues.length <= min(n, 10)
1 <= nums[i] < 10^5
0 <= andValues[j] < 10^5

How to solve Minimum Sum of Values by Dividing Array

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Bitwise AND over a growing window can only clear bits, so for a fixed right endpoint there are at most about 17 distinct AND values across all left endpoints when values stay below 10^5. A dynamic program over (segments used, prefix length) therefore needs only a tiny map from AND value to the best previous-boundary cost instead of scanning every left endpoint.

Why brute force is not enough

A direct dp[j][i] that tries every left endpoint for the jth segment ending at i costs O(m * n^2), about 10^9 at n = 10^4, and a recursive partition search without memoization is exponential.

Approach

  1. Define the state as the minimum cost after cutting the first i elements into exactly j segments matching andValues[1..j], where a segment costs its last element; the answer is the state at (m, n) or -1 if unreachable.
  2. For each layer j, sweep i left to right maintaining a small map from the AND of nums[l..i] over all left endpoints l to the smallest previous-layer cost at position l - 1.
  3. To advance to i, AND every key with nums[i], merging duplicates by minimum, then insert nums[i] paired with the previous layer's cost at i - 1 to represent a segment starting at i. The map then describes every achievable AND ending at i with its cheapest prefix.
  4. If the map contains andValues[j], the state at (j, i) is that cost plus nums[i]; otherwise infinite. Only two layers are kept.
  5. The base layer treats zero segments over zero elements as cost 0.

Walkthrough of Example 1

nums = [1,4,3,3,2], andValues = [0,3,3,2] → 12

  1. Layer 1 (target 0): prefix ANDs of [1,4,3,3,2] are 1, 0, 0, 0, 0, so one segment over the first i elements is valid for i = 2..5 with costs 4, 3, 3, 2; i = 1 is impossible.
  2. Layer 2 (target 3): ending at position 3 only the single element 3 has AND 3, cost 3 + 4 = 7. Ending at position 4, starts at 3 or 4 both give AND 3 with best previous cost 3, so 6. Position 5 (value 2) has no AND 3.
  3. Layer 3 (target 3): ending at position 4 starting at 4 gives AND 3 with previous cost 7, so 10; starting at 3 needs a layer-2 cost at prefix 2, which is infinite.
  4. Layer 4 (target 2): ending at position 5 starting at 5 gives AND 2 with previous cost 10, so 12; starting at 4 gives AND 2 but needs a layer-3 cost at prefix 3, infinite.
  5. The state at (4, 5) is 12, the partition [1,4] | [3] | [3] | [2].

Time and space

Time O(n * m * log V) · Space O(n + log V). For each of m layers and n positions the map holds at most log V distinct AND values, about 17 for V = 10^5; two rows of n costs plus the small map are the storage.

Interview pitfalls

  • Charging the sum of a segment instead of only its last element.
  • Allowing empty segments or a first segment that does not start at index 0; every element belongs to exactly one of the m contiguous segments in order.
  • Failing to merge map entries that collapse to the same AND after ANDing with nums[i], letting worse costs shadow better ones.
  • Using a full array indexed by AND value per position instead of a map of at most 17 keys, which is slower and wasteful.

Follow-up questions interviewers ask

  • How would the solution change for bitwise OR, where bits can only be set?
  • Can you recover the actual partition, and what bookkeeping does that need?
  • If m could approach n, how would you cut per-layer work, for example by iterating only positions where the previous layer is finite?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to Minimum Sum of Values by Dividing Array.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.