# Minimum Sum of Values by Dividing Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sum-of-values-by-dividing-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree, Queue
---
## Problem
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`.

**Example 1:**

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

**Output:** 12

**Explanation:**

The only possible way to divide `nums` is:

1. `[1,4]` as `1 & 4 == 0`.
2. `[3]` as the bitwise `AND` of a single element subarray is that element itself.
3. `[3]` as the bitwise `AND` of a single element subarray is that element itself.
4. `[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:**

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

**Output:** 17

**Explanation:**

There are three ways to divide `nums`:

1. `[[2,3,5],[7,7,7],[5]]` with the sum of the values `5 + 7 + 5 == 17`.
2. `[[2,3,5,7],[7,7],[5]]` with the sum of the values `7 + 7 + 5 == 19`.
3. `[[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:**

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

**Output:** \-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`

# Approaches
## Brute-force Recursion
This approach explores all possible ways to partition the `nums` array into `m` subarrays. A recursive function `solve(i, j)` is defined, which tries to find a valid partition for the suffix of `nums` starting at index `i` and the suffix of `andValues` starting at index `j`.
**Time:** Exponential, roughly `O(C(n-1, m-1) * n)`, where `C` is the binomial coefficient. This is because it explores every possible partition of the `nums` array into `m` subarrays. · **Space:** `O(m)` due to the recursion stack depth, as the recursion goes as deep as the number of subarrays `m`.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient and will result in a Time Limit Exceeded (TLE) error for most of the constraints.
### Explanation
The function `solve(i, j)` aims to find the minimum sum for partitioning `nums[i:]` to match `andValues[j:]`.

It iterates through all possible end points `k` for the `j`-th subarray, which starts at `i`.

For each `k`, it calculates the bitwise AND of `nums[i...k]`.

If this AND value equals `andValues[j]`, it makes a recursive call `solve(k+1, j+1)` to solve the rest of the problem.

The total sum for this partition is `nums[k]` (the value of the current subarray) plus the result of the recursive call.

The function returns the minimum sum found among all valid `k`.

Base cases handle scenarios where we have successfully partitioned the whole array or run out of elements.
```java
class Solution {
    private static final int INF = Integer.MAX_VALUE / 2;
    private int[] nums;
    private int[] andValues;
    private int n, m;

    public int minimumValueSum(int[] nums, int[] andValues) {
        this.nums = nums;
        this.andValues = andValues;
        this.n = nums.length;
        this.m = andValues.length;

        int result = solve(0, 0);
        return result >= INF ? -1 : result;
    }

    private int solve(int i, int j) {
        // Base case: successfully formed m subarrays
        if (j == m) {
            return (i == n) ? 0 : INF;
        }
        // Base case: ran out of numbers in nums but still need to form subarrays
        if (i == n) {
            return INF;
        }

        int minSum = INF;
        int currentAnd = -1; // Represents all bits set to 1

        // Iterate through all possible end points 'k' for the j-th subarray
        for (int k = i; k < n; k++) {
            if (currentAnd == -1) {
                currentAnd = nums[k];
            } else {
                currentAnd &= nums[k];
            }

            if (currentAnd == andValues[j]) {
                int restSum = solve(k + 1, j + 1);
                if (restSum < INF) {
                    minSum = Math.min(minSum, nums[k] + restSum);
                }
            }
        }

        return minSum;
    }
}
```
### Algorithm
- Define a recursive function `solve(startIndex, andIndex)`.
- Base Case 1: If `andIndex == m` (all `andValues` are matched), return 0 if `startIndex == n` (all `nums` are used), otherwise return a large value (infinity) to signify an invalid partition.
- Base Case 2: If `startIndex == n` but `andIndex < m`, return infinity as it's impossible to form more subarrays.
- Initialize `minSum = infinity` and `currentAnd = -1` (all bits 1).
- Loop `k` from `startIndex` to `n-1`:
    - Update `currentAnd` by ANDing with `nums[k]`.
    - If `currentAnd == andValues[andIndex]`:
        - Recursively call `res = solve(k + 1, andIndex + 1)`.
        - If `res` is not infinity, update `minSum = min(minSum, nums[k] + res)`.
- Return `minSum`.
- The initial call is `solve(0, 0)`. If it returns infinity, no solution exists, so return -1.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems, avoiding redundant calculations. The state of our DP is defined by `(i, j)`, representing the subproblem for `nums[i:]` and `andValues[j:]`.
**Time:** `O(n^2 * m)`. There are `O(n*m)` states to compute. Each state computation involves a loop that can run up to `n` times in the worst case. · **Space:** `O(n * m)` for the memoization table. The recursion stack depth also contributes, but it's dominated by the table size.
**Pros:** Much faster than brute-force by avoiding recomputation of overlapping subproblems.; A standard and systematic way to solve problems with optimal substructure.
**Cons:** The time complexity is still too high for the given constraints (`n <= 10^4`), leading to a Time Limit Exceeded (TLE) verdict.
### Explanation
We use a 2D array `memo[i][j]` to store the result of `solve(i, j)`. Before computing `solve(i, j)`, we check if `memo[i][j]` already has a computed value. If so, we return it directly.

The recursive structure is the same as the brute-force approach. The function iterates through possible endpoints `k` for the current subarray, and if a valid subarray is found, it makes a recursive call for the rest of the arrays.

An optimization is added: since the bitwise AND is a non-increasing operation, if the `currentAnd` value becomes "incompatible" with `andValues[j]`, we can stop extending the current subarray. A value `x` is incompatible with `y` if `(x & y) != y`, meaning `x` has a zero bit where `y` has a one bit. Once this happens, ANDing with more numbers won't fix it.
```java
import java.util.Arrays;

class Solution {
    private static final int INF = Integer.MAX_VALUE / 2;
    private int[] nums;
    private int[] andValues;
    private int n, m;
    private int[][] memo;

    public int minimumValueSum(int[] nums, int[] andValues) {
        this.nums = nums;
        this.andValues = andValues;
        this.n = nums.length;
        this.m = andValues.length;
        this.memo = new int[n][m];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        int result = solve(0, 0);
        return result >= INF ? -1 : result;
    }

    private int solve(int i, int j) {
        if (j == m) {
            return (i == n) ? 0 : INF;
        }
        if (i == n) {
            return INF;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int minSum = INF;
        int currentAnd = -1;

        for (int k = i; k < n; k++) {
            if (currentAnd == -1) {
                currentAnd = nums[k];
            } else {
                currentAnd &= nums[k];
            }

            // Optimization: if currentAnd can't possibly become andValues[j]
            if ((currentAnd & andValues[j]) != andValues[j]) {
                break;
            }

            if (currentAnd == andValues[j]) {
                int restSum = solve(k + 1, j + 1);
                if (restSum < INF) {
                    minSum = Math.min(minSum, nums[k] + restSum);
                }
            }
        }

        return memo[i][j] = minSum;
    }
}
```
### Algorithm
- Create a memoization table `memo[n+1][m+1]` initialized with a value indicating "not computed" (e.g., -1).
- Define a recursive function `solve(startIndex, andIndex)`.
- Base Cases: Same as brute-force.
- Check memoization: If `memo[startIndex][andIndex]` is already computed, return it.
- Initialize `minSum = infinity` and `currentAnd = -1`.
- Loop `k` from `startIndex` to `n-1`:
    - Update `currentAnd &= nums[k]`.
    - **Optimization**: If `(currentAnd & andValues[andIndex]) != andValues[andIndex]`, break the loop as further ANDing will not satisfy the condition.
    - If `currentAnd == andValues[andIndex]`:
        - Recursively call `res = solve(k + 1, andIndex + 1)`.
        - If `res` is not infinity, update `minSum = min(minSum, nums[k] + res)`.
- Store the result: `memo[startIndex][andIndex] = minSum`.
- Return `minSum`.

## Optimized DP with Segment Jumps and Range Minimum Query
This is the most efficient approach, which optimizes the transition of the DP state. Instead of iterating through all possible endpoints `k` one by one, it leverages a key property of the bitwise AND operation: for a fixed starting index `i`, the value of `nums[i] & ... & nums[k]` changes a limited number of times as `k` increases. We can "jump" between these change points.
**Time:** `O(m * (n * log(n) + n * L^2))`, where `L` is `log(max(nums))`. For each of the `m` stages, we build a segment tree in `O(n log n)` and then compute `n` DP states. Each DP state takes `O(L^2)` because the inner while loop runs `O(L)` times, and finding `p_next` takes `O(L)`. · **Space:** `O(n * (m + L))`. This is for the `dp` table (`n*m`), the `next_zero` table (`n*L`), and the segment tree (`4*n`).
**Pros:** Highly efficient and passes the given constraints.; A clever optimization based on the properties of bitwise operations and standard data structures.
**Cons:** Significantly more complex to understand and implement correctly compared to simpler DP approaches.
### Explanation
The DP state `dp[i][j]` remains the same: the minimum sum for `nums[i:]` and `andValues[j:]`. We compute it iteratively from `j = m-1` down to `0`.

**Key Idea**: For a fixed `i`, the sequence of AND-prefix values `A(i, k) = nums[i] & ... & nums[k]` has at most `O(log(max(nums)))` distinct values. We can iterate through segments of `k` where `A(i, k)` is constant.

**Precomputation**: We precompute an array `next_zero[i][b]`, which stores the index of the first element at or after `i` that has a 0 in the `b`-th bit. This helps us quickly find the next index where the AND-prefix value will change. This takes `O(n * L)` time, where `L` is the number of bits (e.g., 17 for values up to 10^5).

**DP Transition**: To compute `dp[i][j]`, we iterate through the segments of constant AND-prefix values starting from `i`.
- Let the current segment be `[p_curr, p_next - 1]`, where the AND-prefix value is `v`.
- If `v == andValues[j]`, we have found a range of valid endpoints for the current subarray. We need to find the minimum of `nums[k] + dp[k+1][j+1]` for `k` in this range.

**Range Minimum Query (RMQ)**: This subproblem is a classic RMQ. For each `j`, before computing the `dp` values, we build a data structure (like a Segment Tree) on the array `costs[k] = nums[k] + dp[k+1][j+1]`. This allows us to query the minimum in a range in `O(log n)`.

The overall process involves iterating `j` from `m-1` to `0`. For each `j`, we build the RMQ structure and then compute `dp[i][j]` for all `i` using the segment jumping technique.
```java
import java.util.Arrays;

class Solution {
    private static final int INF = Integer.MAX_VALUE / 2;
    private static final int BITS = 17;

    public int minimumValueSum(int[] nums, int[] andValues) {
        int n = nums.length;
        int m = andValues.length;

        int[][] next_zero = new int[n + 1][BITS];
        for (int b = 0; b < BITS; b++) {
            next_zero[n][b] = n;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int b = 0; b < BITS; b++) {
                if (((nums[i] >> b) & 1) == 0) {
                    next_zero[i][b] = i;
                } else {
                    next_zero[i][b] = next_zero[i + 1][b];
                }
            }
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        dp[n][m] = 0;

        for (int j = m - 1; j >= 0; j--) {
            int[] costs = new int[n];
            for (int k = 0; k < n; k++) {
                costs[k] = (dp[k + 1][j + 1] < INF) ? nums[k] + dp[k + 1][j + 1] : INF;
            }
            SegmentTree st = new SegmentTree(costs);

            for (int i = n - 1; i >= 0; i--) {
                int p_curr = i;
                int and_val = -1;
                while (p_curr < n) {
                    and_val &= nums[p_curr];
                    if ((and_val & andValues[j]) != andValues[j]) {
                        break;
                    }

                    int p_next = n;
                    for (int b = 0; b < BITS; b++) {
                        if (((and_val >> b) & 1) == 1) {
                            p_next = Math.min(p_next, next_zero[p_curr + 1][b]);
                        }
                    }

                    if (and_val == andValues[j]) {
                        int min_cost = st.query(p_curr, p_next - 1);
                        if (min_cost < INF) {
                            dp[i][j] = Math.min(dp[i][j], min_cost);
                        }
                    }
                    p_curr = p_next;
                }
            }
        }

        return dp[0][0] >= INF ? -1 : dp[0][0];
    }
}

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 0, 0, n - 1);
    }

    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = start + (end - start) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public int query(int l, int r) {
        if (l > r) return Integer.MAX_VALUE / 2;
        return query(0, 0, n - 1, l, r);
    }

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return Integer.MAX_VALUE / 2;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        int p1 = query(2 * node + 1, start, mid, l, r);
        int p2 = query(2 * node + 2, mid + 1, end, l, r);
        return Math.min(p1, p2);
    }
}
```
### Algorithm
- Precompute `next_zero[i][b]` for all `i` and bits `b`.
- Initialize a DP table `dp[n+1][m+1]` with a large value (infinity). Set `dp[n][m] = 0`.
- Loop `j` from `m-1` down to `0`:
    - Create an array `costs` where `costs[k] = (k < n ? nums[k] : infinity) + (k+1 <= n ? dp[k+1][j+1] : infinity)`.
    - Build an RMQ data structure (e.g., Segment Tree) on the `costs` array.
    - Loop `i` from `n-1` down to `0`:
        - Initialize `p_curr = i`, `and_val = -1`, `min_res = infinity`.
        - Loop while `p_curr < n`:
            - `and_val &= nums[p_curr]`.
            - If `(and_val & andValues[j]) != andValues[j]`, break.
            - Find `p_next`, the end of the segment where the AND-prefix from `i` remains `and_val`. This is done using `next_zero` in `O(L)` time.
            - If `and_val == andValues[j]`:
                - Query the RMQ structure on the `costs` array for the range `[p_curr, p_next - 1]` to get `min_cost_in_segment`.
                - Update `min_res = min(min_res, min_cost_in_segment)`.
            - Set `p_curr = p_next`.
        - Set `dp[i][j] = min_res`.
- The final answer is `dp[0][0]`. If it's infinity, return -1.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
private
  int[] andValues;
private
  final int inf = 1 << 29;
private
  Map<Long, Integer> f = new HashMap<>();
public
  int minimumValueSum(int[] nums, int[] andValues) {
    this.nums = nums;
    this.andValues = andValues;
    int ans = dfs(0, 0, -1);
    return ans >= inf ? -1 : ans;
  }
private
  int dfs(int i, int j, int a) {
    if (nums.length - i < andValues.length - j) {
      return inf;
    }
    if (j == andValues.length) {
      return i == nums.length ? 0 : inf;
    }
    a &= nums[i];
    if (a < andValues[j]) {
      return inf;
    }
    long key = (long)i << 36 | (long)j << 32 | a;
    if (f.containsKey(key)) {
      return f.get(key);
    }
    int ans = dfs(i + 1, j, a);
    if (a == andValues[j]) {
      ans = Math.min(ans, dfs(i + 1, j + 1, -1) + nums[i]);
    }
    f.put(key, ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumValueSum(vector<int> &nums, vector<int> &andValues) {
    this->nums = nums;
    this->andValues = andValues;
    n = nums.size();
    m = andValues.size();
    int ans = dfs(0, 0, -1);
    return ans >= inf ? -1 : ans;
  }

private:
  vector<int> nums;
  vector<int> andValues;
  int n;
  int m;
  const int inf = 1 << 29;
  unordered_map<long long, int> f;
  int dfs(int i, int j, int a) {
    if (n - i < m - j) {
      return inf;
    }
    if (j == m) {
      return i == n ? 0 : inf;
    }
    a &= nums[i];
    if (a < andValues[j]) {
      return inf;
    }
    long long key = (long long)i << 36 | (long long)j << 32 | a;
    if (f.contains(key)) {
      return f[key];
    }
    int ans = dfs(i + 1, j, a);
    if (a == andValues[j]) {
      ans = min(ans, dfs(i + 1, j + 1, -1) + nums[i]);
    }
    return f[key] = ans;
  }
};

```

### Python

```python
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

```