Problem statement

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

The value of an array is its last element.

Split nums into exactly m disjoint contiguous non-empty subarrays so that for the i-th subarray [l_i, r_i], the bitwise AND of its elements equals andValues[i]: nums[l_i] & nums[l_i + 1] & … & nums[r_i] == andValues[i] for every 1 <= i <= m.

Return the minimum possible sum of the values of the m subarrays, or -1 if no such split exists.

Example 1

Input: nums = [1,4,3,3,2], andValues = [0,3,3,2]
Output: 12
Explanation: Split as [1,4], [3], [3], [2]: 1 & 4 = 0, and the values are 4 + 3 + 3 + 2 = 12.

Example 2

Input: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]
Output: 17
Explanation: [2,3,5], [7,7,7], [5] gives 5 + 7 + 5 = 17, the cheapest valid split.

Example 3

Input: nums = [1,2,3,4], andValues = [2]
Output: -1
Explanation: One piece must cover everything, and 1 & 2 & 3 & 4 = 0.

Constraints

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

Hints for Minimum Sum of Values by Dividing Array

1. Hint 1

   Think of the split piece by piece: f_j[i] = cheapest way to cover the first i elements with the first j pieces.

2. Hint 2

   For a fixed end i, the AND of nums[l..i] only loses bits as l moves left, so it takes at most about 17 distinct values — and each value covers a contiguous range of starts l.

3. Hint 3

   Keep, for the current end, the list of distinct AND values of subarrays ending there, each with the minimum of f_{j} over its starts. Extending the end by one element ANDs every value with it and merges equal neighbours. If the target appears, f_{j+1}[i+1] = that minimum + nums[i].

How to solve Minimum Sum of Values by Dividing Array

Process the pieces one at a time. For each new piece, sweep the end position and maintain the distinct AND values of all subarrays ending there — at most log(max) of them — each paired with the cheapest prefix cost among the starts that produce it.

Approach

1. f[0] = 0, f[i] = ∞ for i > 0: the cost of covering a prefix of length i with the pieces placed so far.
2. For each target t = andValues[j]: start an empty list of pairs (and, best). For i = 1..n, with x = nums[i-1], build the new list: first (x, f[i-1]) (the piece starting at i-1), then every old pair as (and & x, best), merging a pair into the previous one when the AND values are equal (keep the smaller best).
3. If some pair has and == t and a finite best, set g[i] = best + x; otherwise g[i] = ∞.
4. After the sweep, f = g. After all m targets, return f[n], or -1 if it is infinite.

Why it works

Every subarray ending at i - 1 starts at some l; its AND is one of the list's values, and the list groups starts by that value, so best is exactly the minimum of f[l] over the starts that produce it. Adding a piece only adds its last element to the cost, which is fixed once the end is fixed. Since ANDs only lose bits as the subarray grows, the values are strictly decreasing along the list and there are at most about 17 of them.

Complexity

• Time — O(m · n · log(max(nums)))
• Space — O(n)

Pitfalls

• The cost of a piece is its last element, not its AND.
• Every element must belong to some piece — the last piece must end at n - 1.
• A start l whose prefix f[l] is infinite must not make an otherwise impossible state look reachable.

Reference solution

Python

from typing import List

def minimumValueSum(nums: List[int], andValues: List[int]) -> int:
    INF = float('inf')
    n = len(nums)
    f = [INF] * (n + 1)
    f[0] = 0
    for target in andValues:
        g = [INF] * (n + 1)
        vals, mins = [], []  # distinct ANDs of subarrays ending here, cheapest prefix for each
        for i in range(1, n + 1):
            x = nums[i - 1]
            nv, nm = [x], [f[i - 1]]
            for v, m in zip(vals, mins):
                w = v & x
                if w == nv[-1]:
                    if m < nm[-1]:
                        nm[-1] = m
                else:
                    nv.append(w)
                    nm.append(m)
            vals, mins = nv, nm
            for v, m in zip(vals, mins):
                if v == target:
                    if m < INF:
                        g[i] = m + x
                    break
        f = g
    return f[n] if f[n] < INF else -1

Java

public static int minimumValueSum(int[] nums, int[] andValues) {
    final int INF = Integer.MAX_VALUE;
    int n = nums.length;
    int[] f = new int[n + 1];
    Arrays.fill(f, INF);
    f[0] = 0;
    int[] vals = new int[40], mins = new int[40], nv = new int[40], nm = new int[40];
    for (int target : andValues) {
        int[] g = new int[n + 1];
        Arrays.fill(g, INF);
        int len = 0; // distinct ANDs of subarrays ending here, cheapest prefix for each
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int nl = 0;
            nv[nl] = x; nm[nl] = f[i - 1]; nl++;
            for (int t = 0; t < len; t++) {
                int w = vals[t] & x;
                if (w == nv[nl - 1]) nm[nl - 1] = Math.min(nm[nl - 1], mins[t]);
                else { nv[nl] = w; nm[nl] = mins[t]; nl++; }
            }
            int[] tmp = vals; vals = nv; nv = tmp;
            tmp = mins; mins = nm; nm = tmp;
            len = nl;
            for (int t = 0; t < len; t++) {
                if (vals[t] == target) {
                    if (mins[t] < INF) g[i] = mins[t] + x;
                    break;
                }
            }
        }
        f = g;
    }
    return f[n] < INF ? f[n] : -1;
}

C++

int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
    const int INF = INT_MAX;
    int n = nums.size();
    vector<int> f(n + 1, INF);
    f[0] = 0;
    for (int target : andValues) {
        vector<int> g(n + 1, INF);
        vector<pair<int, int>> cur; // distinct ANDs of subarrays ending here, cheapest prefix for each
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            vector<pair<int, int>> nxt;
            nxt.push_back({x, f[i - 1]});
            for (auto& pr : cur) {
                int w = pr.first & x;
                if (w == nxt.back().first) nxt.back().second = min(nxt.back().second, pr.second);
                else nxt.push_back({w, pr.second});
            }
            cur.swap(nxt);
            for (auto& pr : cur) {
                if (pr.first == target) {
                    if (pr.second < INF) g[i] = pr.second + x;
                    break;
                }
            }
        }
        f = g;
    }
    return f[n] < INF ? f[n] : -1;
}

JavaScript

var minimumValueSum = function(nums, andValues) {
    var INF = 1e15, n = nums.length;
    var f = new Array(n + 1).fill(INF);
    f[0] = 0;
    for (var j = 0; j < andValues.length; j++) {
        var target = andValues[j];
        var g = new Array(n + 1).fill(INF);
        var vals = [], mins = []; // distinct ANDs of subarrays ending here, cheapest prefix for each
        for (var i = 1; i <= n; i++) {
            var x = nums[i - 1];
            var nv = [x], nm = [f[i - 1]];
            for (var t = 0; t < vals.length; t++) {
                var w = vals[t] & x;
                if (w === nv[nv.length - 1]) {
                    if (mins[t] < nm[nm.length - 1]) nm[nm.length - 1] = mins[t];
                } else {
                    nv.push(w);
                    nm.push(mins[t]);
                }
            }
            vals = nv;
            mins = nm;
            for (var t = 0; t < vals.length; t++) {
                if (vals[t] === target) {
                    if (mins[t] < INF) g[i] = mins[t] + x;
                    break;
                }
            }
        }
        f = g;
    }
    return f[n] < INF ? f[n] : -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard